Knapsack Problem에는 두 가지 종류가 있다.

1. Fractional Knapsack Problem
2. 0/1 Knapsack Problem

Fractional Knapsack Problem 의 경우에는 그리디로 해결할 수 있다. 하지만 0/1 Knapsack Problem 은 DP로 풀어야 한다.

문제 아이디어

Fractional Knapsack Problem 의 경우, 아이템을 쪼개서 넣을 수 있으므로 무게당 가치가 높은 아이템부터 넣으면 해결할 수 있다.

하지만 0/1 Knapsack Problem 은 아이템을 쪼개서 넣을 수 없으므로 아이템을 넣는 경우와 넣지 않는 경우에 대해 모두 탐색해야 한다.

1. 배낭에 아이템을 넣는 경우
2. 배낭에 아이템을 넣지 않는 경우

배낭에 아이템을 넣을 수 있는 경우 1, 2번의 값중 더 큰 값을 저장하면 된다.
배낭에 아이템을 넣을 수 없는 경우, 선택지는 2번밖에 없다.

예제

총 아이템은 4개가 있고, 배낭은 최대 7의 무게를 견딜 수 있다.

아이템은 아래와 같다.

번호	무게	가치
1	6	13
2	4	8
3	3	6
4	5	12

dp 테이블의 행을 아이템의 번호, 열을 배낭의 무게라고 정하자.
그럼 dp[i][j] 는 i 번째 아이템까지 생각했을 때, 배낭의 무게가 j 이하인 가치의 최댓값이라고 정의할 수 있다.

점화식

따라서 점화식은 아래와 같이 정의할 수 있다.

dp[i][j] = max(dp[i-1][j-1] + value[i], dp[i-1][j])

dp 테이블

아이템\무게	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	0	0
2	0	0	0	0	0	0	0	0
3	0	0	0	0	0	0	0	0
4	0	0	0	0	0	0	0	0

먼저 1번 아이템을 고려해보자. 1번 아이템은 무게가 6이므로 배낭의 무게가 5 이하일 때에는 아이템을 넣을 수 없다.
따라서 아래와 같이 표를 채워 넣을 수 있다.

아이템\무게	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0	0	0	0	0	0	0	0
3	0	0	0	0	0	0	0	0
4	0	0	0	0	0	0	0	0

이제 2번 아이템을 생각해보자. 2번 아이템은 무게가 4이므로 배낭의 무게가 3이하일 때는 넣을 수 없다.
그리고 무게가 6이상일 때에는 1번 아이템을 넣는 선택지도 고려해야 한다.
두 아이템의 무게를 합하면 6+4=10 이므로 1, 2번 아이템을 모두 배낭에 넣을 수는 없다.
1번 아이템을 넣는게 더 가치가 높은지, 현재 2번 아이템을 넣는게 더 가치가 높은지 선택해야 한다.

아이템\무게	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13
3	0	0	0	0	0	0	0	0
4	0	0	0	0	0	0	0	0

이제 3번째 아이템을 생각해보자. 3번째 아이템은 무게가 3, 가치가 6이므로 아래와 같이 테이블을 채울 수 있다.

여기서는 1번 아이템만 넣으면 가치가 13이지만, 2, 3번 아이템을 넣으면 무게는 7이고 가치가 14가 되므로 2, 3번 아이템을 넣는 것이 가치가 높다. 따라서 dp[3][7]=14가 된다.

아이템\무게	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13
3	0	0	0	6	8	8	13	14
4	0	0	0	0	0	0	0	0

4번 아이템까지 표를 채우면 아래와 같고 dp[4][7] = 14이므로 배낭에 넣을 수 있는 아이템의 최대 가치는 14임을 구할 수 있다.

아이템\무게	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13
3	0	0	0	6	8	8	13	13
4	0	0	0	6	8	12	13	14

코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;
using ll = long long;

#define MX_N 100
#define MX_K 100000

int w[MX_N+1];
int v[MX_N+1];

int dp[MX_N+1][MX_K+1];

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

    int n, k;
    cin >> n >> k;

    for(int i= 1; i <= n; i++){
        cin >> w[i] >> v[i];
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= k; j++){
            if(j >= w[i]){ // 배낭에 물건을 넣을 수 있는 경우
                dp[i][j] = max(dp[i-1][j-w[i]] + v[i], dp[i-1][j]);
            }else{// 배낭에 물건을 넣을 수 없는 경우
                dp[i][j] = dp[i-1][j];
            }
        }
    }

    cout << dp[n][k];
}

문제

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