0-1 Knapsack problem

Problem

도둑이 보석가게에 부피 W인 배낭을 매고 침입했다. 도둑은 매장에 진열된 보석의 크기 v와 가격 p을 알고 있다. 이때 도둑이 훔친 보석의 가격의 최대 합은 얼마인가?

0-1 Knapsack 문제의 이해

---

한번 생각해보면 매장에 진열된 보석들의 가격을 기준으로 정렬한 후 가장 큰 가격이 있는 순대로 집어넣으면 될 것처럼 보인다. 그러나 아래와 같은 반례를 만들 수 있다.

• 크기 10의 배낭이 있다. 다음 보석들이 (크기,가치)의 순으로 입력이 주어진다.

보석 = (10, 10), (8, 5), (5, 3), (3, 5), (2, 3)

• 이때, 가장 큰 가치를 가진 보석부터 넣으면 10이 최대가 되겠지만 크기 5, 3, 2를 넣으면 11의 가치를 얻을 수 있다.

그래서 DP(Dynamic Programming)를 이용하여 이 문제를 해결할 수 있다. dp의 정의는 다음과 같다.

• dp[i][j] : i번째 보석까지 배낭에 넣었을 때 j크기가 되는 경우의 최대 가치

$i$번째 보석을 배낭에 넣었을 때 $j$의 크기가 된다면 다음 두 가지 경우를 생각할 수 있다.

1. $j$의 크기가 배낭의 크기를 넘어서는 경우 $(j > W)$
2. 배낭의 크기를 넘지 않아 최대 가격을 갱신하게 되는 경우
   • $dp[i][j]=max(dp[i-1][j-v_i]+p_i, \space dp[i-1][j])$

위의 경우를 다시 정리하면 다음과 같다.
$dp[i][j] = \cases{dp[i-1][j], & \text{if } j+v_i > W \cr \max(dp[i-1][j-v_i]+p_i, \space dp[i-1][j]), & \text{if } j+v_i ≤ W}$

0-1 Knapsack 구현

---

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

int main() {
    int n=5;
    int W=10;
    vector<int> v={0,10,8,5,3,2}; // 인덱스 1부터 시작
    vector<int> p={0,10,5,3,5,3};
    vector<vector<int> > dp(n+1,vector<int>(W+1,0));

    for(int i=1;i<=n;i++) {
        for(int j=1;j<=W;j++) {
            if(j-v[i]>=0) { // 배낭에 넣을 수 있다면
                dp[i][j]=max(dp[i-1][j-v[i]]+p[i],dp[i-1][j]);
            }
            else dp[i][j]=dp[i-1][j];
        }
    }

    cout<<dp[n][W];
    return 0;
}

0-1 Knapsack 성능

---

반복문을 보면 $N$번 반복하면서 $W$를 다시 반복한다. 따라서 $O(NW)$의 시간 복잡도를 가진다.