[KnapSack] 백준 12865 : 평범한 배낭

12865번: 평범한 배낭 (acmicpc.net)

12865번: 평범한 배낭

 

트리 구조로 생각하자. 주어진 입력들이 있고 내가 첫 번째 짐부터 마지막 짐까지 차례대로 순회한다고 생각하자.

 

N번째 짐을 만났을 때, 내가 선택할 수 있는 경우는 2가지다. 넣던가, 안 넣던가. 

 

즉, (가방 수)*(무게)의 dp 배열이 있고, 배열에는 그 무게를 들었을 때 최대로 누릴 수 있는 효용이 들어 있다고 생각할 때

 

1. 가방에 안 넣는 경우

=> dp[i-1][j] 가 0이 아닌 경우, 그 값을 그대로 dp[i][j]에 저장해 준다. 

 

2. 가방에 넣는 경우

=> dp[i-1][j]가 0이 아닌 경우, (=이전에 짐이 미리 들어 있는 경우) j(==기존 무게)+weight[i] 가 무게 허용 범위를 초과하는지 여부를 검토하고, 초과하지 않는다면 dp[i][j+weight[i]]에 dp[i][j-1]+value[i]를 넣어 준다.

N번째 짐을 맨 처음으로 넣는 경우를 고려하기 위해, dp[i][weight[i]]에 value[i]를 넣어 준다.

 

이렇게 하면, dp배열의 마지막 줄은 가방에 짐을 넣는 모든 경우의 수와 각 무게에 따른 효용이 저장되게 되므로, 그 중 최대값을 출력하면 된다.

 

----------------------------------------------------------------------------------------------------------------------------------------------------------------

이렇게 했을 때 틀렸는데, 그 이유는 내가 구하려는 것이 '가방에 최대 무게를 초과하지 않고 넣을 수 있는 짐들의 조합 중 가장 큰 효용' 이기 때문이다. 가령 똑같이 7kg을 넣더라도 그 효용은 다를 수 있고, 만일 그렇다면 더 작은 효용을 가진 쪽은 더 이상 dp배열을 채울 때 고려할 필요가 없다. 따라서 1~2번 과정에서 '효용의 최대값을 구해서 넣는' 절차가 추가되어야 한다.

 

#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> weight(N + 1);
    vector<int> value(N + 1);

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

    vector<vector<int>> dp(N + 1, vector<int>(K + 1));

    for (int i = 1; i < N + 1; i++)
    {
        for (int j = 1; j < K + 1; j++)
        {
            if (dp[i - 1][j] != 0)
            {
                // 1. 이전까지 추가된 짐에 현재 짐 추가 2. 이전까지 추가된 짐만 두고 현재 짐은 추가 x
                dp[i][j] = max(dp[i][j], dp[i - 1][j]);

                if (j + weight[i] <= K)
                {
                    dp[i][j + weight[i]] = max(dp[i - 1][j] + value[i], dp[i][j + weight[i]]);
                }
            }
        }
        // 3. 이번 짐만 처음으로 추가하는 경우
        if (weight[i] <= K)
        {
            dp[i][weight[i]] = max(value[i], dp[i][weight[i]]);
        }
    }

    int ans = 0;
    for (int i = K; i > 0; i--)
    {
        ans = max(ans, dp[N][i]);
    }

    cout << ans;
}