백준 12865번 평범한 배낭

🔒[문제 url]

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

🔑알고리즘

가방의 무게를 $1$부터 $k$까지 늘려가며, $i$번 물건을 넣을 지 안 넣을 지 결정하게 된다.
물건을 넣고자 할 때, 경우의 수는 다음과같이 세 가지이다.
1. 현재 물건이 한계 무게를 초과하여 못 넣는 경우
2. 현재 물건을 안 넣는 것이 이득인 경우
3. 현재 물건을 넣는 것이 이득인 경우

dp[i][j] 무게 $j$까지 담을 때, $i$번 물건을 담을 지 여부를 결정했을 때 최대 가치를 의미한다.
따라서, 현재 물건을 가방에 담을 수 있는 경우 점화식은 다음과같다.

dp[i][j] = max(dp[i-1][j],dp[i-1][j-obj[i].first] + obj[i].second);

즉, (현재 물건을 담지 않는 경우)와 (현재 물건을 담는 경우) 중 가치의 최대값이다.

🐾부분 코드

점화식을 이해했다면 코드 설명은 따로 필요없어 생략한다.

🪄전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int,int> pii;
int n,k;
vector<pii> obj;
int dp[101][100'001];

void INPUT()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    obj.push_back({0,0});
    for(int i = 0; i < n; i++)
    {
        int w, v; cin >> w >> v;
        obj.push_back({w,v});
    }
}


void SOLVE()
{
    for(int i = 1; i <= n; i++)
    {// 모든 물건을 순회하며
        for(int j = 1; j <= k; j++)
        {// 가방에 담을 무게를 늘려가며
            
            // 1) 현재 물건이 한계 무게를 초과한다면, 담지 않는다.
            if(j - obj[i].first < 0) dp[i][j] = dp[i-1][j];
            // 2,3) 현재 물건을 선택하지 않거나, 선택하거나
            else dp[i][j] = max(dp[i-1][j],
                                dp[i-1][j-obj[i].first] + obj[i].second);
        }
    }
    cout << dp[n][k];
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

dp는 풀기도 진짜 어려운데 설명하기가 더 어렵다ㅋㅋㅋㅋㅋ...
참고로 knapsack 알고리즘은 많은 dp문제에서 유용하니 잘 알고 넘어가도록 하자. 2달 전에 풀었다가 처참히 깨진 문제인데, 이제는 가볍게 풀리니 기분이 좋았다.