[백준 12865] 평범한 배낭 (C++)

문제

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

12865번: 평범한 배낭

풀이

유명한 0-1 배낭 문제입니다.

dp[i][j]의 의미는 i개까지의 물건을 넣는 경우에서 무게가 j일때 가치의 최대값입니다.

예제 입력으로 분석해보겠습니다.

n / k	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0
1	0	0	0	0	0	13	13
2	0	0	0	8	8	13	13
3	0	0	6	8	8	13	14
4	0	0	6	8	12	13	14

먼저 n = 0일때는 넣을 수 있는 물건이 없으므로 모든 무게에서 가치는 0입니다.

n = 1 일 때는 무게가 6, 가치가 13인 물건만 넣을 수 있으므로 1~5무게에서는 가치 0, 6~7무게에서는 가치 13입니다.

n = 2 일 때는 무게가 4, 가치가 8인 물건이 추가됩니다. 아래의 점화식에 따라 dp[i][j]의 값을 결정합니다.

1) 물건을 넣을 수 없는 경우에는 dp[i-1][j]의 값을 그대로 넣습니다.

2) 물건을 넣을 수 있는 경우에는 dp[i-1][j]의 값과 dp[i-w[i]]+v[i]의 값을 비교하여 더 큰 값을 넣습니다.

이 과정을 반복했을 때 dp[n][k]의 값이 가치의 최댓값이 됩니다.

소스 코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
 
int dp[101][100001];
int w[101];
int v[101];
int n, k;
 
int main()
{
    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], dp[i - 1][j - w[i]] + v[i]);
            //물건을 넣을 수 없는 경우
            else
                dp[i][j] = dp[i - 1][j];
        }
    }
    cout << dp[n][k];
    return 0;
}