Knapsack Problem Dynamic Programming C++

 PS를 좋아하는 사람이라면 한 번쯤은 Knapsack Problem에 대해 들어본 적이 있을 것이다. DP를 활용하는 대표적인 문제이기도 하고, 알고리즘을 공부하기에도 좋은 문제이다.

Knapsack Problem :  주어진 물건들에 대해 그 가치와 무게가 주어져있을 때,  무게의 합이 담을 수 있는 최대 무게를 넘기지 않고 가치의 합이 최대가 되도록 배낭에 담기 위해서는 어떤 물건을 담아야하는가?

자세한 설명 : https://en.wikipedia.org/wiki/Knapsack_problem

Knapsack problem - Wikipedia

 

 이 문제를 접근하는 대표적인 방법은 총 3가지가 있다. 먼저 흔히 '노가다' 라고 불리는 Brute-Force 를 사용하는 방법이 있다. 또, (가치/무게)가 큰 물건부터 담는 Greedy 방법을 쓸 수도 있다. 마지막으로 머리가 조금 더 좋은 사람은 점화식을 세워서 Dynamic Programming 으로 풀 수도 있다.

 

1. Brute-Force

 Brute-Force는 모든 경우에 대해서 다 해보는 방법이다. 물건의 개수(N)가 충분히 작을 때는 이 방법이 좋을 수도 있다. 하지만 가능한 전체 경우의 수가 2^N - 1가지이므로,  O(2^N)의 시간복잡도를 가져 N이 조금만 커져도 연산 횟수가 너무 많아지게 된다. 따라서 이 방법은 적절하지 않다.

 

2. Greedy

 Greedy는 Brute-Force보다는 연산횟수가 훨씬 적고 훨씬 합리적인 것 같아보인다. 하지만 역시 Greedy가 항상 전체의 최적의 답을 보장하진 않으므로 반례가 존재한다. 아주 쉬운 반례로 최대 한계 무게가 6이고, 무게,가치의 순서쌍이 (w,v) = (4,5),(3,3),(3,3)인 물건 3개가 있을 때 (가치/무게)를 기준으로 Greedy를 적용하면 (4,5) 하나만 선택해 가치의 합이 5이지만, (3,3),(3,3)을 선택하는 것이 가치의 합이 6으로 더 좋다. 따라서 이 방법도 적절하지 않다.

 

3. Dynamic Programming

 DP로 이 문제를 풀려면 점화식을 잘 세워야한다. 먼저 dp[i][j]를 정의해주자.

dp[i][j] = |1번부터 i번 물건까지 최대 무게 j로 담을 때 가능한 가치의 합 중 최대가치|

 초항부터 살펴보면 자명하게 j=0인 경우, 물건을 담을 수 없으므로 0이다. 또, i=1인 경우 j가 1번째 물건의 무게(w1)보다 크거나 같다면 dp[i][j]는 1번째 물건의 가치(v1)가 될 것이고, 아니라면 0이 될 것이다.

dp[i][0] = 0

dp[1][j] = 0    if j ≥ w1
            = v1  elsewise

 이제 좀 더 일반적인 경우에 대해 살펴보자. i번째 물건을 넣으려고 할 때 만약 i번째 물건의 무게(wi)가 j보다 크다면 이 물건을 어떻게 해도 넣지 못할 것이다. 따라서 이 경우 dp[i][j]는 1번부터 i-1번까지의 물건만 이용할 수밖에 없으므로 dp[i-1][j]이다. 다른 경우에는 i번째 물건을 넣는 경우와 넣지 않는 경우로 생각해볼 수 있다. 먼저 더 쉬운 넣지 않는 경우에 대해 살펴보면 자명하게 최대 가치는 dp[i-1][j]일 것이다. i번째 물건을 포함하는 경우, 먼저 1번째 물건부터 i-1번째 물건을 채웠을 때 무게가 j-wi보다는 작거나 같아야할 것이다(그래야지 i번째 물건을 넣었을 때 무게가 j를 초과하지 않으므로). 따라서 넣기 전까지의 최대 가치는 dp[i-1][j-wi]이고 i번째 물건을 넣으면 그 가치가 dp[i-1][j-wi] + vi가 된다. 따라서 두 경우중 더 가치가 큰 것을 선택해주면 된다.

dp[i][j] = dp[i-1][j]                                        if wi > j
           = max(dp[i-1][j], dp[i-1][j-wi] + vi)    elsewise

 

코드(백준 12865 평범한 배낭)

#include <iostream>
#include <algorithm>
using namespace std;

int N,W,thing[101][2],dp[101][100001];
int main()
{
    cin>>N>>W;
    for(int i=1;i<=N;i++)
    {
        cin>>thing[i][0]>>thing[i][1];
    }
    for(int j=1;j<=W;j++)
    {
        if(thing[1][0] <= j)
        {
            dp[1][j] = thing[1][1];
        }

        for(int i=2;i<=N;i++)
        {
            if(thing[i][0] > j)
            {
                dp[i][j] = dp[i-1][j];
            }
            else
            {
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-thing[i][0]]+thing[i][1]);
            }
        }
    }
    cout<<dp[N][W];
}