Knapsack Problem

유명한 knapsack 문제 :

도둑이 박물관에서 물건을 훔치려고 할 때, single knapsack만 가지고 있는 도둑은 어떤 걸 훔쳐야 가장 큰 값을 훔칠 수 있을까?

 

 

knapsack 문제에는 두가지 버전이 있다

1. 0-1 knapsack problem                   -> on&off, 담거나 담지 않거나

아이템을 쪼갤 수 없다. 이 문제는 Dynamic programming으로 풀 수 있다. Greedy는 불가.

 

2. Fractional knapsack problem        -> 자를 수 있다고 생각

아이템을 쪼갤 수 있다. 이 문제는 Greedy, Dynamic programming 모두 가능하다.

 

 

1. Fractional knapsack problem

fractional knapsack problem을 풀기 위해서는 먼저 각 item에 대한 파운드 당 vi/wi 값을 계산해야 한다.

greedy 알고리즘을 통해 도둑은 파운드 당 가장 큰 가치를 가진 항목을 최대한 많이 가져옵니다. 그 다음에 knapsack에 자리가 남는다면 그 다음으로 큰 가치를 지닌 물건을 가능한 많이 가져가고, 이를 담을 수 없을 때까지 반복합니다.

 

 

 

---

 

 

2. 0-1 knapsack problem

knapsack이 담을 수 있는 최대 용량을 W라고 하고, n개의 아이템으로 구성된 세트 S가 있다고 하자.

각 아이템 i는 wi의 무게와, bi의 benefit이 있다고 한다.

 

이 문제를 bruth force로 풀자고 하면, 모든 가능성을 보기 때문에 running time이 Θ(2^n )로 너무 오래 걸린다.

또한, greedy 알고리즘은 이 분제에 적합하지 않다.

때문에 우리는 이 문제를 풀기 위해서는 Dynamic algorithm을 사용한다.

 

 

여기서 우리는 subproblem을 올바르게 정의할 필요가 있다.

만약에, 아이템이 n개 있다고 할 때 subproblem을 1~k까지로 정의하면 올바르지 않다. 왜냐하면

subproblem을 잘 못 선택한 경우

 

이와 같이, S4는 S5의 part가 아니기 때문에 결함이 있다. 우리는 하위 문제를 위한 새로운 정의가 필요하다.

하위 문제를 정의하기 위해서 각 아이템의 number 뿐만 아니라 weight도 고려하여 정한다.

 

 

 

그렇다면, B[k,w] 로 하위문제를 계산할 것이다. (B-얻을 수 있는 이익, k-1~k까지의 item을 고려, w-knapsack의 weight)

원래는 optimal substructure -> sub problem 정의 -> recursive formula 순서인데,

이 문제에서는 optimal substructure를 만족시킬 수 있도록 문제를 define해야 한다.

 

저 두 케이스는 k번째 item의 weight인 wk가 W를 넘느냐 안넘느냐에 따라 다르다.

-  첫 번째, B [k-1, W]는 wk>W 이어서 k를 포함시키지 않는 경우이다. k를 포함시키면 총 weight이 W를 넘기 때문에 넣지 않는다.

이 경우에는 B [k, W]=B [k-1, W] 이다.

-  두 번째, wk <=W인 경우다. 여기에서는 k를 집어넣는 경우와 안 집어넣는 경우 둘 중 큰 것으로 고르면 된다. 

B [k, W-1] 는 k를 집어넣은 경우로, 같은 아이템에 적은 weight을 가지고 있는 것이다.

B [k-1, W]는 k를 집어넣지 않는 경우로, 같은 weight에서 k-1개의 아이템까지만 고려한 경우인데, 여기서는 k번째 item의 benefit value인 bk를 더한다.

 

 

 

이 knapsack problem의 pseudocode를 보자면

 

 

 

다음은 예시를 통해 knapsack problem을 DP로 푸는 방법을 알아보겠다.

옆에 사진은 Item 네 개를 DP를 이용하여 knapsack에 적용해 본 것이다.

 

여기서 최종 solution은 7이 된다.

 

 

 

 

 

 

 

 

 

 

 

 

 

---

 

 

3. Branch and  Bound - Best First Search

 

knapsack - branch and bound

모든 노드를 방문하지 않고, 그것이 가치가 있는지 없는지를 결정한다.

 

각 노드에서, 세가지의 변수를 계산해야 한다.

benefit : 해당 노드까지의 benefit value 합계

weight : 해당 노드까지의 weight 합계

bound : 해당 노드를 넘어 확장함으로써 얻을 수 있는 이익에 대한 상한선 (이걸 계산하는 것이 key point!)

 

bound 값은, 이 아이템들을 쪼갤 수 있다고 가정하고, 쪼갠 물건도 그 단위 비율만큼의 가치가 있다고 가정할 때, pi/wi가 쓰인다.

단위 무게당 이익이 가장 큰 순서대로 물건을 최대한 쪼개서 넣는 것이 이상적이다.

 

 

 

 

 

 

 

 

 

 

 

 

 

또한 max_benefit이라는 global 변수도 필요하다. max_benefit는 benefit의 최댓값이다.

먼저, 초기에는 max_benefit = 0이다.

그 다음 각 노드에서, weight<W이라면  max_benefit = max(max_benefit, benefit) 이다. 

 

max_benefit과 bound를 비교해서 expand 할지 말지를 결정한다. bound가 max_benefit보다 작으면 expand 하지 않는다.

 

 

노드는 promising (이 노드를 넘어서 expand 한다) 할 것인지, nonpromising (여기서 멈추겠다) 할 것인지 평가한다.

  - nonpromising

Case 1 : bound <= max_benefit  

             bound가 max_benefit보다 작거나 같아서 굳이 expand 할 필요가 없다.

Case 2 :weight > W

             현재 knapsack에 아이템이 너무 커서 집어넣을 수 없을 때

 

  - promising

bound > max_benefit 또는 weight < W 일 때 promising 한다.

 

 

기본적으로 BFS를 적용하고 최대 bound가 있는 promising하고 unexpanded한 노드를 선택한다.

 

다음은 사진으로 branch and bound하는 단계를 알아보자

 

(1,2) 노드 같은 경우에는, 1번 아이템이 들어가지 않기 때문에 bound를 계산하면,

 

tot_weight = 5+10=15 <= W

bound = $30+ $50 + (16-15) * 10/5 = 82