98. 가방문제(냅색 알고리즘) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★☆☆☆

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, m, a, b;
	cin >> n >> m;
	
	vector<pair<int, int>> V;
	vector<int> Bag(m+1, 0);
	
	for(int i = 1; i <= n; i++)
	{
		cin >> a >> b;
		V.push_back(make_pair(a, b));
	}
	
	for(int i = 0; i < V.size(); i++)
	{
		int w = V[i].first;
		int v = V[i].second;
		for(int j = 0; j < Bag.size(); j++)
		{
			if(j - w < 0) continue;
			
			if(Bag[j] < Bag[j-w] + v)
				Bag[j] = Bag[j-w] + v;
		}
	}
	
	cout << Bag[m] << "\n";
	
	return 0;
}

1. 가치가 12인 5g 짜리의 보석만 가방에 넣는다고 가정하자. 넣는 방법은 다음과 같다.

• j 는 가방의 담을 수 있는 무게이다. Bag의 윗 줄이 j의 값이다. 0 ~ 4g까지 담을 수 있는 가방은 5g 짜리 보석을 담을 수 없다. j = 5 부터 담을 수 있게 된다.
• 담을 수 있는 가방이라면 담을 수 있는 남은 무게(j) = (담을 수 있는 남은 무게 - 보석의 무게)의 가치 + 보석의 가치이다. 아래 그림으로 설명하겠다.

5g 짜리 가방은 5g짜리 보석 하나를 담을 수 있다. 이는 Bag[5] = Bag[5-5] + 12 라는 의미이다. Bag[0] = 0 이므로 0 + 12 = 12가 된다.

6 ~ 9 까지도 같게 작용한다.

10은 Bag[10] = Bag[5] + 12 = 12 + 12 = 24가 된다. Bag[11] = Bag[6] + 12 = 12 + 12 = 24가 된다.

 

 

2. 가치가 8인 3g짜리 보석을 담아보자. 3g 짜리 가방부터 시작할 것이다.

5g 짜리 가방을 보자. 원래대로라면 Bag[5] = Bag[2] + 8 = 8 이어야한다. 근데 가치가 12가 되도록 담을 수 있게 Bag[5] = 12로 되어있다. 이럴 때는 두 가지를 비교해서 가치가 더 높은 값을 할당하면 된다.

 

위와 같은 조건대로라면 Bag[6] = Bag[3] + 8 = 8 + 8 = 16 이다. 12보다 크므로 16을 할당한다.

이렇게 반복하면 최종 표는 다음과 같다.

 

Bag[11] 을 출력하면 된다.