냅색 알고리즘 (Knapsack Algorithm)

1. 냅색 알고리즘이란?

제한된 자원을 최적화된 방식으로 배분하여 최대 가치를 얻게되는 알고리즘

2.문제 유형

I) 종류를 무한정 담을 수 있는 경우

II) 종류를 한 개밖에 담지 못하는 경우

3. 예시

종류가 4개인 보석과 담을 수 있는 한계값이 11인 경우

입력 값
4 11 // 보석 종류의 개수와 무게 한계값
5 12 // 보석의 무게와 가치
3 8
6 14
4 8

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

int main(int argc, char** argv) 
{
	ios_base::sync_with_stdio(false);
	
	int v, w; // 보석의 종류, 무게 한계
	cin >> v >> w;
	
	vector<int> dy(w+1, 0);
	
	for(int i=0; i<v; i++)
	{
		int m, p;
		
		cin >> m >> p;
		
		for(int j=m; j<=w; j++ )
		{
			dy[j] = max(dy[j], dy[j-m]+p);
		}
	}
	
	cout << dy[w];
	
	return 0;
}

Dynamic table의 인덱스는 가방의 최대 무게이다

Dynamic table의 값은 최대 무게의 최대 가치이다.

dy[j] = max(dy[j], dy[j-m]+p) 보석의 무게 m = 5일 경우 무게가 5인 보석은 무조건 하나를 담고 시작한다.

1.첫 번째 아이템(무게 5, 가치 12)이 반영된 후

j = 5 에서

dy[5] = max(dy[5], dy[5-5] + 12) = max(0, 12) = 12

→ 무게 5짜리 가방에 보석을 하나 담음

j = 6…11 에서도

dy[j] = max(0, dy[j-5] + 12) = 12

→ 이미 담은 보석을 “재사용”하여 무게 6부터 11까지 전부 가치 12로 초기화

이후 아이템들도 같은 방식으로

각 아이템마다 j = m 부터 순차 갱신

dy[j-m] 값이 이미 갱신된 뒤값을 재사용하므로

동일 아이템을 무한히 반복해서 담을 수 있음

위와 같이 “앞쪽(j=m→W) 순회”를 통해 완전 냅색이 구현되며

동일 아이템을 반복 담아도 제약 없이 최댓값을 찾아낼 수 있다.