[백준] 12865번 c++ 평범한 배낭

풀이)

이 문제는 0-1 배낭 문제로 이를 해결하기위해 물건을 하나씩 고려하며 배낭 용량에 따른 최대 가치를 계산합니다.

역순으로 탐색하면서,  물건을 넣지 않았을 때는 dp[w]이며,

물건을 넣었을 때는 dp[w-weight[i]] +value[i]  해당 물건의 무게를 빼주고, 가치를 더해주는 방식입니다.

 

코드)

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

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


	vector<int>weight(n+1);
	vector<int>value(n+1);
	vector<int>dp(k+1, 0); // k무게에서의 최대가치

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

	for (int i = 1; i <= n; ++i) {
		for (int w = k; w >= weight[i]; w--) {
			dp[w] = max(dp[w], dp[w - weight[i]] + value[i]);

		}
	}
	cout << dp[k];


}