평범한 배낭 12865

문제

접근 방법

DP 문제에 가장 대표적인 Knapsack 문제이다.

	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	6	8	12	13	14

예제대로 작성해본 표이다.
이것으론 아직 해결책을 못찾을 것 같다.
3, 7 4, 5 6, 7가 있고
최대 무게는 9라고 생각하고 작성해보자.

	0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	7	7	7	7	7	7	7
2	0	0	0	7	7	7	7	12	12	12
3	0	0	0	7	7	7	7	12	12	14

첫 예제에 4번째 선택 5KG을 보면 가치가 12인 것을 볼 수 있다.
즉 기존에 값보단 자신의 값이 더 나을 때가 있다는 것이다.

3번째 선택 7KG을 보면 4KG(8)+3KG(6)인 것을 볼 수 있다. 3번째 선택은 3KG이다.
4KG의 값은 어디에서 찾을 수 있을까? 4KG일 때 최고의 가치는 이미 기록됐다. 배열에서 4번째 인덱스를 확인해보면 된다.

N 번째의 값과 (N-무게) 번째의 값+ 현재 물건의 값
둘 중 비싼 값을 골라서 집어넣어 주면 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, K;
    cin >> N >> K;
    vector<int> dp(K + 1);
    while (N--)
    {
        int W, V;
        cin >> W >> V;
        for (int i = K; i >= W; --i)
        {
            dp[i] = max(dp[i], dp[i - W] + V);
        }
    }
    cout << dp[K];
    return 0;
}

풀이

1차원 배열로 작성하였다.
1차원 배열로 할 시 뒤에서부터 접근해야 한다는 것을 알게 됐다. 앞에서부터 접근하면 새로운 값으로 갱신되기 때문이다.
접근 방법에서 이야기했듯이
기존값과 (현재 무게-넣으려는 무게)의 위치에 최고 가치 + 넣으려는 가치를 비교하여 DP를 채워주면 된다.

이번 문제에서도 cpp이 제대로 작동 안 했는데 재설치하여 해결했다. 다음 문제부터는 문제없이 작동하면 좋겠다.