🖊️ 문제

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

---

🖊️ 풀이

각각 무게 W, 가치 V를 가지는 짐 N개를, 무게 K 이하로 최대한 가치가 높게 배낭에 넣고 싶다.

무게가 w인 짐을 배낭에 넣었을 때, (k-w)까지의 짐을 같이 넣을 수 있다.

만약 i번째 짐이 무게가 너무 커서 아예 배낭에 못넣는다면, 해당 짐은 처리하지 못하므로 i-1번째까지 넣는 것과 동일하다 (아예 못넣음)

dp[i][w] = dp[i-1][w]

아니라면, 이제 처리해야되는데
i번째 짐을 배낭에 넣거나 / 안넣거나.

1. i번째 짐을 배낭에 안넣는다면?

그냥 i-1번째 짐을 넣었을 때가 최대
dp[i][w] = dp[i-1][w]

2. i번째 짐을 배낭에 넣는다면?

그 때의 최댓값 dp[i][w]는, i번째 짐의 가치 v 와 무게 k - i번째 짐의 무게까지 넣었을 때의 최댓값을 더한 것.

dp[i][w] = arr[i][1] + dp[i-1][w-arr[i][0]]

그래서, i번째 배낭에 짐을 넣거나, 안넣는 경우 중 더 가치가 큰 것을 선택하면 된다.

생각을 좀 많이 했던 문제..
며칠 후에 한 번 더 풀어봐야겠당.

#include <iostream>
using namespace std;

int dp[101][100'001] = { 0, };
int arr[101][2];		// 0 : w || 1 : v

int main()
{
	int n, k;
	cin >> n >> k;

	for (int i = 1; i <= n; i++) {
		cin >> arr[i][0] >> arr[i][1];
	}

	for (int i = 1; i <= n; i++) {
		for (int w = 1; w <= k; w++) {
			if (arr[i][0] <= w)
				dp[i][w] = max(dp[i - 1][w], arr[i][1] + dp[i - 1][w - arr[i][0]]);
			else
				dp[i][w] = dp[i - 1][w];
		}
	}
	cout << dp[n][k] << endl;
}