냅색(knapsack) 알고리즘

가방 허용 무게가 정해서 있을 때 가방에 넣을 수 있는 물건들의 최대값을 구할 때.

최대 가치를 가지는 물건을 넣는 식으로 greedy 알고리즘으로 문제를 해결하려고 하면

해결 할 수 없다.

 

ex ) 가방의 허용 무게 7kg. 물건들  (6kg 13) (4kg, 8) (3kg, 6) (5kg, 12) 일 때 (4kg, 8) (3kg, 6) 담는 경우가 정답인데

그리디 알고리즘으로 해결하려고 하면 (6kg 13) 나옴

 

분할가능 냅색 알고리즘

- 담을 물건이 소금 등 분할 가능 할 때 무게당 가치로 정렬하고 그리디 알고리즘을 수행하면 해결 가능

0-1냅색 알고리즘(분할 불가능)

• 담을 물건이 나누어 지지 않을 때 사용하는 알고리즘
• DP 알고리즘으로 점화식 이용
• 2차원 리스트 L 를 만든다. (row : 물건 갯수, col : 가방 허용 무게) 
• 각 물건 갯수, 가방 허용 무게 일 때 최대 가치를 리스트에 담아보면 L(n, k) 가 정답.
• 무게가 w 가치가 v인 물건을 넣을 때 점화식 : L(n, k) = max(L[n-1][k], L[n-1][k-w] + v)