[백준/C,C++] 12865번: 평범한 배낭

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

예제 입력으로 바로 설명드리겠습니다. 물건의 수는 4이고, 버틸 수 있는 무게는 7입니다. 각 물건의 무게와 가치는 6/13, 4/8, 3/6, 5/12 입니다.

	배낭 무게 1	배낭 무게 2	배낭 무게 3	배낭 무게 4	배낭 무게 5	배낭 무게 6	배낭 무게 7
물건1 (6/13)	0	0	0	0	0	13	13
물건2 (4/8)	0	0	0	8	8	13	13
물건3 (3/6)	0	0	6	8	8	13	14
물건4 (5/12)	0	0	6	8	12	13	14

물건3을 넣을지 말지 고민중일때 배낭 무게가 7이면 고려 해봐야 할 물건들의 조합은 다음과 같습니다. 무게 7의 배낭에 포함된 물건들, 무게 1의 배낭에 포함된 물건들 + 무게 6의 배낭에 포함된 물건들, 2 + 5, 3 + 4 즉, 이 합 중에 물건3을 넣는 경우의 가치가 최댓값일 때, 물건3을 넣게 되는 것인데 무게 4의 배낭에 포함된 물건들의 가치는 8로, 물건3을 넣었을땐 가치가 14가 됩니다. 무게 7의 배낭에 넣을 수 있는 물건들의 최대가치는 13이었는데, 물건3을 넣고 더 높은 가치를 추구할 수 있게 됩니다. 이 로직을 그대로 코드로 옮긴 후 물건을 최대로 넣었을때, 배낭의 무게가 최대 일때 값을 출력해주면 됩니다.

#include<iostream>

using namespace std;

#define MAX 101
#define MAX_WEIGHT 100001

int DP[MAX][MAX_WEIGHT];

int main(void)
{
    int N, K; cin >> N >> K;

    for (int i = 1; i <= N; i++) {
        int W, V; cin >> W >> V;
        for (int j = 0; j <= K; j++) {
            if (j < W) {
                DP[i][j] = DP[i - 1][j];
            }
            else {
                DP[i][j] = max(DP[i - 1][j], DP[i - 1][j - W] + V);
            }
        }
    }

    cout << DP[N][K];

    return 0;
}