[백준 12865] 0-1 Knapsack Problem

문제 링크: 12865번 평범한 배낭

https://www.acmicpc.net/problem/12865

 

대표적인 풀이 방법은 2차원 DP 배열을 사용하는 방법으로서, 다음과 같이 생각해볼 수 있다. 참고로 보통은 부피라고 하는데 부피와 가치 둘 다 첫 문자가 v라 부피 대신 무게라고 하자.

 

f(i, j) = 배낭에 넣을 수 있는 최대 무게가 j이고, i번째 물건까지 고려했을 때의, 최대 가치

 

f(i, j)는 어떻게 구할 수 있을까?

 

🤷‍♀️ 먼저, w(i)가 j보다 크다면?

이 때에는 물건 i를 배낭에 넣을 수 없다. 따라서 i번째 물건까지 고려했을 때의 결과는 i-1번째 물건까지 고려했을 때의 결과와 같아야 한다.

즉 f(i, j) = f(i, j-1)

 

🤷‍♀️ 그렇다면, w(j)가 i보다 같거나 작다면?

이 때에는 물건 j를 배낭에 넣을 수 있다. 하지만, 물건 j를 반드시 넣어야 하는 것도, 반드시 빼야만 하는 것도 아니다. 우리는 물건 j를 넣는 경우와 넣지 않는 경우 모두를 계산하여 비교함으로써 최대 가치를 구할 수밖에 없다.

즉 f(i, j) = max(물건 j를 배낭에 넣었을 때의 최대 가치, 물건 j를 배낭에 넣지 않았을 때의 최대 가치)

 

▪ 물건 j를 배낭에 넣었을 때의 최대 가치

일단 빈 배낭에 물건 j를 먼저 넣자. 원래 배낭에 넣을 수 있는 최대 무게는 i였으므로 이제 배낭에 넣을 수 있는 최대 무게는 i-w(j)로 줄어들고, 대신 현재 가치는 0에서 v(j)로 증가했다. 그런데 배낭에 넣을 수 있는 최대 부피가 i-w(j)일 때, 즉 i보다 작을 때의 최대 가치는 이미 구했을 것이다. f(i-w(j), j-1)에 저장되어 있는 것이다.

즉 물건 j를 넣는 경우 최대 가치는 f(i-w(j), j-1) + v(j)

여기서 j-1이라고 하는 것은, j를 넣지 않는 이상 최대 부피를 줄였을 때에도 j는 결코 들어가지 않을 것이기 때문이다. 그렇다면 위의 식에서 j-1 대신 j를 넣어도 될까? 그건 아니다. 이는 같은 물건을 두 번 넣을 수 있음을 의미하기 때문이다.

 

▪ 물건 j를 배낭에 넣지 않았을 때의 최대 가치

이 때에는 w(i)가 j보다 큰 경우와 같다.

즉 물건 j를 넣지 않는 경우 최대 가치는 f(i, j-1)

 

결과적으로 f(i, j) = max(f(i, j-w(j))+v(j), f(i, j-1))임을 알 수 있다.

 

다시, f(i, j)는 어떻게 구할 수 있을까?라는 질문으로 돌아오면 이 질문에 대한 답은 다음과 같이 정리된다.

f(i, j) =
f(i, j-1)   if w(j) > i
max(f(i, j-w(j))+v(j), f(i, j-1))   else

 

for (int maxVolume = 1; maxVolume <= k; maxVolume++) {
    for (int numItem = 1; numItem <= n; numItem++) {
        if (volumes[numItem] > maxVolume) {
            dp[maxVolume][numItem] = dp[maxVolume][numItem-1];
        } else {
            dp[maxVolume][numItem] = max(dp[maxVolume][numItem-1], dp[maxVolume-volumes[numItem]][numItem-1] + values[numItem]);
        }
    }
}

 

그런데 이 방법은 그다지 효율적이지만은 못하다. 위 알고리즘은 공간복잡도가 O(N*K)로서, O(K)로 개선될 여지가 있다.

 

물건 하나씩에 대해서, 배낭에 채울 수 있는 무게를 최댓값에서 최솟값으로 줄여나가면서 DP 테이블을 채워나가보면 개선의 실마리를 발견할 수 있다.

 

f(i) = max(f(i), f(i-w(j))+v(j))

 

현재 살펴보는 물건을 j라 하면, f(i)는 1번부터 j번까지의 물건만 있을 때, 배낭에 담을 수 있는 최대 무게가 i일 때의 최대 가치를 저장하고 있다. 첫 번째 인자는 새롭게 살펴보는 물건을 담지 않을 때, 두 번째 인자는 새롭게 살펴보는 물건을 담았을 때를 표현한다.