#include<iostream>
#include<algorithm>
using namespace std;
int N, K;
int DP[101][100001];
int W[101];
int V[101];
// 점화식 max(DP[i-1][j], DP[i-1][j-W[i]])
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];
}-
물건의 개수를 행으로, 배낭의 용량을 열로 삼고 주어진 개수와 용량에 대한 가치합을 원소로 갖는 2차원 배열 DP 생성
-
테스트 케이스의 입력을 예로 들면
-
1번째 물건의 무게는 6, 가치는 13
-
2번째 물건의 무게는 4, 가치는 8
-
3번째 물건의 무게는 3, 가치는 6
-
4번째 물건의 무게는 5, 가치는 12
-
용량제한이 1이라면
-
1~4번째 짐 모두 담을 수 없음
- DP[1][1] = 0
- DP[2][1] = 0
- DP[3][1] = 0
- DP[4][1] - 0
-
용량제한이 2라면
-
마찬가지로 1~4번째 짐 모두 담을 수 없음
- DP[1][2] = 0
- DP[2][2] = 0
- DP[3][2] = 0
- DP[4][2] = 0
-
용량제한이 3이라면
-
3번째 물건만 담을 수 있음
- DP[1][3] = 0
- DP[2][3] = 0
- DP[3][3] = 6
- DP[4][3] = 6
-
용량제한이 4라면
-
2번째 물건만 담을 수 있음
- DP[1][4] = 0
- DP[2][4] = 8
- DP[3][4] = 8
- DP[4][4] = 8
...
- 문제에서 주어진 입력에서 용량제한은 7
- DP[1][7] = 13
- DP[2][7] = 13 // 1번째 물건만 담음
- DP[3][7] = 14 // 2번째 물건과 3번째 물건을 담음
- DP[4][7] = 14 // 2번째 물건과 3번째 물건을 담음
위 케이스에서 DP[2][7]과 DP[2][7-W[i]] + V[i]을 비교하면
DP[2][7]은 13, DP[2][4] + 6 = 8 + 6 = 14이므로
DP[3][7]은 DP[2][7-W[i]] + V[i]가 된다.
배낭문제 점화식 max(DP[i-1][j], DP[i-1][j-W[i]]) 외워두는 게 편할 듯.
