0-1 knapsack problem

가방에 최대 무게가 있고

 

그 무게 안에 물건을 넣는데

 

물건의 가치가 최대로 넣는 경우를 구하는 문제.

 

Brute force로 문제를 풀면 모든 가능한 부분집합의 경우를 비교해보면 되므로

2의 n번을 비교해보게 된다. 

 

 

예를 들어 보석1, 2, 3, 4 가 있고 각각의 무게와 가치가 있을 때

 

0부터 최대 가방무게 n까지 열의 속성으로 두고 

0부터 최대 보석 가지수를 4개까지 행이 속성으로 두어서

보석 가지 수⑊가방 무게	0	1	2	.. n
0	0	0	0	0
1	0
2	0
3	0
4	0

 이런 식으로 테이블이 만들어진다 생각하고 이해해보면 쉽다.

 

처음에 이 문제를 이해하려고 했을 때 많이 애를 먹었던 부분이

 

왜 보석을 여러개를 안넣고 1개만 넣는거지??였다.

예를들어 보석1의 무게가 1이면 가방 무게가 2이므로 보석1을 2개 넣을 수 있는 것이 아닌가 생각했다.

 

나중에 이해한 것이 보석은 종류당 1개씩만 넣을 수 있는 거였다.ㅋ..

 

 

구하는 법은 i번째 보석을 고려해야할 때  

1. i번째 보석 포함

2. i번째 보석 불포함 

이렇게 두 가지 경우로 나누어서 생각하며 DP를 사용하면 될 것 같았다.

 

좀 더 세분화하면

1. i번째 보석의 무게가 가방의 무게보다 큰 경우

    - i번째 보석을 제외하고 나머지 보석들로 가방을 채운다

2. i번째 보석의 무게가 가방의 무게보다 작은 경우

    2-1) i번째 보석을 포함하여 가방을 채운다

    2-2) 그래도 i번째 보석을 포함하지 않고 가방을 채운다

로 위 세가지 경우에서 가치의 합이 최대인걸 골라서 저장해주며 진행하면 되는 것이다.

 

즉,

i번째 보석까지 고려하고 가방 최대무게 W일 때 최대 가치

= 1번 경우이거나 MAX(2-1경우, 2-2경우)가 되는 것이다.

 

그래서 배낭이 최대로 버틸 수 있는 무게를 W라고 두고

보석 i의 가치를 pi, 무게를 wi라고 두고

K[i, w]를 배낭의 무게가 w일 때 보석1부터 보석i까지 고려해보는 것이라고 하면

K[i, w] = wi>w? K[i-1, w] : max(pi + K[i-1,w-wi], K[i-1,w]) 가 될 것이다. 

 

 

이 문제는 Greedy Algorithm이 항상 최적의 값을 찾을 수 없다는 것을 보여주는 예시중 하나이다.