[C++] 가방문제(냅색 알고리즘) ⭐

📄문제

최고 17kg의 무게를 저장할 수 있는 가방이 있다.

그리고 각각 3kg, 4kg, 7kg, 8kg, 9kg의 무게를 가진 5종류의 보석이 있다.

이 보석들의 가치는 각각 4, 5, 10, 11, 13이다.
이 보석을 가방에 담는데 17kg를 넘지 않으면서 최대의 가치가 되도록 하려면 어떻게 담아야할까요? 

각 종류별 보석의 개수는 무한이 많다. 한 종류의 보석을 여러 번 가방에 담을 수 있다는 뜻입니다.

 

⬇️ 입력

첫 번째 줄은 보석 종류의 개수와 가방에 담을 수 있는 무게의 한계값이 주어진다.
두 번째 줄부터 각 보석의 무게와 가치가 주어진다.
가방의 저장무게는 1000kg을 넘지 않는다. 보석의 개수는 30개 이내이다.

4 11 5 12 3 8 6 14 4 8

 

⬆️ 출력

첫 번째 줄에 가방에 담을 수 있는 보석의 최대가치를 출력한다.

28

 

📝 풀이

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

int w[30]; // weight
int v[30]; // value

int dp[1001];

int main()
{
	ios_base::sync_with_stdio(false);

	int N, M, maxValue;
	cin >> N >> M;

	for (int i = 0; i < N; ++i)
		cin >> w[i] >> v[i];

	for (int i = 0; i < N; ++i)
	{
		int weight = w[i];
		int value = v[i];

		// 현재 무게부터 시작하여 가방의 마지막까지 반복하여 더 큰 가치를 갱신
		for (int j = weight; j <= M; ++j)
		{
			if (dp[j] < dp[j - weight] + value)
				dp[j] = dp[j - weight] + value;

			maxValue = max(maxValue, dp[j]);
		}
	}

	cout << maxValue;
}

• 냅색 알고리즘을 적용하여 가방에 최대 무게를 dp로 만들어 내부에는 보석을 넣었을 때 가치를 누적합니다.
• 반복을 통해 최대 가치를 갱신하여 답을 구합니다.