[알고리즘] knapsack 알고리즘

Knapsack 알고리즘

• knapsack 알고리즘은 제한된자원으로 최대의 이득을 얻는 유명한 다이나믹 프로그래밍 문제이다.
• knapsack 알고리즘은 크게 3가지 방식으로 나뉜다.

  1. Fractional knapsack : 물건을 분할해서 가방에 담을 수 있음
     -> 단순히 무게당 가치가 높은 것을 우선해서 담기만 하면됨
  2. 0-1 knapsack : 특정 물건을 통째로 담거나 담지 않아야 함
  3. unbounded knapsack : 각 종류의 물건을 여러번 사용 가능

• 아래에서 2, 3번에 대한 알고리즘을 다룬다.

1) 0-1 knapsack 알고리즘

• knapsack 알고리즘의 대표적인 문제이다.
• 아래처럼 점화식을 세울 수 있다.

  • DP[i][w] = i번째 보석까지 w이하만큼 담았을 때 최대 가치를 저장
  • DP[i][w] = MAX(DP[i-1][w], DP[i-1][w - w[i]] + v[i])

• 위 점화식의 각 케이스를 고려해보면 아래와 같다.

  1. DP[i][w] = DP[i-1][w] : 현재 물건을 담지 않는 것이 더 가치가 높은 경우
  2. DP[i][w] = DP[i-1][w - w[i]] + v[i] : 현재 물건을 담는 것이 더 가치가 높은 경우

• 예시 코드

for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= K; j++) {
                if (arr[i].w > j)  //현재 물건이 무게를 초과하는 경우 
                	dp[i][j] = dp[i-1][j];
                else               //현재 물건을 담을 수 있는 경우 
                	dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - arr[i].w] + arr[i].v);
            }
}

2) unbounded knapsack 알고리즘

• 0-1 knapsack 알고리즘보다 단순하게 무게 조건만으로 1차원 DP 배열을 통해 점화식을 세울 수 있다

  DP[w] = w만큼 담았을 때 최대 가치를 저장
  DP[w] = MAX(DP[w], DP[w - w[i]] + v[i]) (i : 1~N까지 반복)

• 예시 코드

for (int i = 1; i <= N; i++) {
            for (int j = 0; j <= K; j++) {
                if (arr[i].w <= j)  //현재 물건이 무게를 초과하는 경우 
                	dp[j] = Math.max(dp[j - arr[i].w] + arr[i].v, dp[j]);
            }
}