DP를 배울 때 등장하는 아주 유명한 문제!

배낭 알고리즘이다.

 

가장 비싸고 무게가 적은 물건들을 최대한 많이 가져가야한다!

조건은!

1) 물건을 부분적으로 담을 수는 없다

2) 물건들은 모두 한개씩만 있다. 예로 똑같은 반지가 2개일 수 없다..(?)

 

도둑은 현재 15의 무게를 담을 수 있는 배낭을 가지고 있습니다. 그리고 아래와 같이 그 집의 물건이 있지요. 

 

items	weight	value
[0]	5	8
[1]	8	11
[2]	3	3
[3]	4	6
[4]	2	4

이 상황에서 도둑이 훔쳐갈 수 있는 최대의 값을 구하는 것입니다.

 

어떻게 도둑을 도와줄것인가?

아 그냥 무게가 가장 적은거 순서대로 훔쳐가면 되지 않을까요?

라고 생각하신다면 다시 한번 생각해봅시다.

위의 물건들을 가장 작은 무게가 나가는 것을 훔쳐가게 된다면 items[4], items[2], items[3], items[0]만 가져갈 수 있고, 총 가치는 21이 되고 총 용량은 14가 됩니다.

하지만 items[0], items[1], items[4]를 선택한다면 총 가치는 23이 되고, 용량은 15로 더 비싼물건을 훔칠 수 있습니다.

 

그렇기 때문에 무게가 덜 나가는 순으로 정렬해서 문제를 해결할 수가 없는것이죠.

그래서 단순 무식하게 한번 접근해봅시다.

도둑은 그 물건을 훔쳐갈 수 있느냐, 훔쳐갈 수 없느냐 이 둘만 고려합니다. 

 

1) 훔쳐갈때 

만약 어떤 물건을 훔쳐갈 수 있다고 한다면 현재 무게가 그 물건의 무게만큼 무거워지요. 하지만 배낭 용량을 초과할 수는 없습니다. 그럴땐 그 물건을 배낭에 담을 수가 없습니다.

현재 그 물건들을 배열로 표현(items)하고, 어떤 물건을 고려 할때 그 아이템의 인덱스를 pos라고 합시다. 그리고 현재 용량을 capacity라고 해봅시다. V는 그 물건의 가치, W는 그 물건의 용량이라고 친다면 우리는 이런 식을 쓸 수 있습니다.

 

knapsack(pos + 1, capacity - items[pos][W]) + items[pos][V]

 

knapsack이라는 함수는 현재 물건 이후 가장 큰 값을 반환합니다. 그러니까 당연히 용량(capacity)는 그 물건의 무게(items[pos][W])만큼 줄어들 것이고, 그 반환된 가장 큰 값에서 현재 물건의 가치를 더함으로써 지금 이 물건을 훔쳤을때 얻을 수 있는 값을 얻을 수 있습니다.

 

2) 훔쳐가지 않을 때

그리고 또 그냥 그 물건을 안가져갈 수도 있습니다. 그럴때는 현재 무게가 그대로 유지되면서 다음 물건을 고려하는 겁니다.

 

그러니 아래의 식이 가능합니다.

 

knapsack(pos + 1, capacity )

 

 

1)훔쳐갈 경우와 2)훔쳐가지 않을 경우 중에서 가장 큰 값이 우리가 원하는 답이 되는 것이죠.

 

코드

이런 프로그램을 구현한 것이 바로 아래 소스 코드입니다.