Knapsack - 제한 용량에 최대 가치 채우기

Knapsack 문제 일반화

10kg 배낭에 넣을 수 있는 물건이 4개가 있고 각 물건의 무게와 가치는 다음과 같다.

• 무게 : 5, 4, 6, 3
• 가치 : 10, 40, 30, 50

여기서 각 물건은 넣거나 넣지 않을 수 있다.

 

최대 가치를 구해야 하므로 가장 작은 문제 부터 최대 가치를 만들어서 10kg 문제까지 해결해보자

여기서 가장 작은 문제는 1kg 배낭에 채울 수 있는 최대 가치라고 정의하자.

 

1. (5, 10) 의 물건

1 ~ 4kg 배낭엔 채울 수 없으므로 가치는 0

5kg 배낭으로 가치는 10

 

2. (5,10) (4,40) 의 물건

1 ~ 3kg 배낭엔 채울 수 없으므로 가치는 0

4 ~ 8kg 배낭엔 (4, 40)을 채울 수 있으므로 가치는 40

9 ~ 10kg 배낭엔 (4, 40), (5, 10) 추가할 수 있으므로 가치는 50

 

표를 그려 보면

...

나머지도 채워보면

표를 통해 각 셀은 wkg 배낭에 채울 수 있는 최대 가치를 의미하는 것을 알 수 있다.

 

각 셀의 규칙성을 파악해보기 위해 K열 3행에 주목해보자

 

4kg 물건을 넣기전 가방의 무게와 가치를 체크한다.

이제 물건을 넣을지 말지 판단하는데 판단 기준은 제한 용량이다.

현재 9kg 배낭이므로 4kg 물건을 넣을 수 있고 넣기 전 가방의 최대 가치는 G열 3행이다. (넣기 전 가방의 최대 가치를 알아 내는게 핵심이다.)

 

규칙성을 통해 물건을 넣을 수 있는 경우, 없는 경우를 나눠 다음과 같은 점화식을 만들 수 있다.

 

제한 용량 = w

현재 배낭의 무게 = k

물건의 개수 = n

각 물건 번호(인덱스) = i

각 물건의 무게 = wi

각 물건의 가치 = vi

 

넣을 수 있는 경우

 

넣을 수 없는 경우