백준 12865 평범한 배낭 (배낭 문제)

이 문제는 유명한 DP문제 중 하나로 0-1 knapsack problem입니다. 배낭에 무게 제한을 넘지 않으면서 내용물의 가치의 합이 최대가 되는 물건들의 부분집합을 구하는 문제입니다. 물건을 쪼갤 수는 없습니다.

 

모든 부분집합을 구하는 경우는 $O(2^n)$의 시간이 걸리기 때문에 시간초과가 나게 됩니다.

점화식

배낭 문제에서 dp의 점화식은 다음과 같습니다.

dp배열에서 x축은 물건의 인덱스 번호, y축은 자연수인 무게 값이 들어가게 됩니다.

기본적인 아이디어는 i 번째 물건을 집어 넣는 경우와 넣지 않는 경우 중에서 큰 값을 dp테이블에 저장하는 것입니다.

 

예제를 살펴보겠습니다.

가방의 무게 제한은 7이고 물건의 무게와 가치가 다음과 같이 주어졌습니다.

6 13
4 8
3 6
5 12

첫 번째 줄을 채워봅시다. 무게 제한이 6이 안된다면 첫 번째 물건을 담을 수 없고 6 이상인 경우에 물건을 담고 13의 가치를 당을 수 있습니다.

i \ w	1	2	3	4	5	6	7
1	0	0	0	0	0	13	13
2
3
4

두 번째 줄을 채우는 경우입니다. dp[2][6]을 보면 무게가 6인 경우 가치가 8인 두 번째 물건을 담는 것 보다 가치가 13인 첫 번째 물건을 담는게 더 큰 가치의 물건을 가방에 담을 수 있습니다. (dp[i - 1] 이 더 큰 경우)

i \ w	1	2	3	4	5	6	7
1	0	0	0	0	0	13	13
2	0	0	0	8	8	13	13
3
4

이런 식으로 테이블을 전부 채우게 되면 다음과 같습니다. dp[3][7]을 보면 dp[2][4] + value[3] = 14이므로 (2번 물건과 3번 물건을 담는 경우) 1번 물건 하나를 담는 것 보다 더 가치가 크므로 14를 저장한 것을 볼 수 있습니다. 

i \ w	1	2	3	4	5	6	7
1	0	0	0	0	0	13	13
2	0	0	0	8	8	13	13
3	0	0	6	8	8	13	14
4	0	0	6	8	12	13	14

시간복잡도

$O(nW)$이며 다항시간 내에 문제를 해결할 수 없다고 알려져 있습니다. (NP-complete)

코드

#include <iostream>

using namespace std;

int dp[102][100002];
int value[102];
int weight[102];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> weight[i] >> value[i];
    }

    for (int i = 1; i <= n; i++)
    {
        for (int w = 1; w <= k; w++)
        {
            if (weight[i] <= w)
            {
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weight[i]] + value[i]);
            }
            else
            {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    cout << dp[n][k] << '\n';

    return 0;
}