[백준 12865] 평범한 배낭

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

---

해설

이번 문제는 일정한 무게와 가치가 주어질 때, 가치의 합이 최대가 되면서 짐을 고르게 하는 전형적인 냅색 문제이다.

 

max(dp[i-1][j], dp[i-1][j - w[i]] + v[i])

냅색 점화식

 

소스코드

 

#include <iostream>
#include <algorithm>
using namespace std;
int dp[101][100001];
int w[101];
int v[101];
int main() {
	int n, k; cin >> n >> k;
	for (int i = 1; i <= n; i++) 
		cin >> w[i] >> v[i];
	for (int i = 1; i <= n; i++) {
		for (int ww = 0; ww < w[i]; ww++)
			dp[i][ww] = dp[i - 1][ww];
		for (int j = w[i]; j <= k; j++)
			dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]);
	}
		cout << dp[n][k] << '\n';
}