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

문제 링크

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

 

 

코드 구현

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int N, K;
	cin >> N >> K;

	// dp[w] = 무게가 w일 때의 최대 가치
	vector<int> dp(K + 1, 0);

	for (int i = 0; i < N; i++)
	{
		int weight, value;
		cin >> weight >> value;

		for (int w = K; w >= weight; --w)
		{
			// 넣지 않는 경우 / 넣는 경우
			dp[w] = max(dp[w], dp[w - weight] + value);
		}
	}

	cout << dp[K] << endl;

	return 0;

}

 

 

해결 방법

동적 해결법 dp 배열을 사용하여 최대 무게 K에서의 최대 가치를 배열에 저장하였다. 

• 입력 받은 아이템을 넣는 경우 : dp[w-weight] + value 
• 넣지 않는 경우 : dp[w] (그대로)

w를 뒤에서부터 감소시킨 이유는 중복 선택을 방지하기 위해서이다.