그리디 알고리즘(4)[ 부분 배낭 문제(Fractional Knapsa) ]

Knapsack문제는 최대의 가치를 갖도록 '한정된 용량의' 배낭에 넣을 물건들을 정하는 문제다.

 

부분 배낭은 물건을 통째로 넣는게 아닌, 각 부분만 담는 것이 허용된다. 

ㅡ> 단위 무게당 값을 구한뒤에 제일 비싼 것부터 순차적으로 담으면 끝.

 

시간 복잡도는 O(nlogn) 

---

Fractional Knapsack 의사코드(슈도코드, pseudocode)

 

입력: n개의 물건과 각 물건의 무게와 가치, 배낭의 용량C

출력: 배낭에 담은 물건 리스트 L과 배낭에 담은 물건의 가치 합 v

1  각 물건의 단위 무게당 가치를 계산한다.

2  물건들으 단위 무게당 가치를 기준으로 내림차순으로 정렬하고 정렬된 물건 리스트를 S라 하자

3  L= ∅, w=0, v=0

// L은 배낭에 담은 물건 리스트, w는 배낭에 담긴 물건들의 무게의 합, v는 배낭에 담긴 물건들의 가치의 합

4  S에서 단위 무게당 가치가 가장 큰 물건 x를 가져온다.

5  while((w+x의 무게) <= C) {

6          x를 L에 추가시킨다.

7          w = w + x의 무게

8          v = v + x의 가치

9          x를 S에서 제거한다.

10        S에서 단위 무게당 가치가 가장 큰 물건 x를 가져온다. 

     }

11 if((C-w) > 0) {  // 배낭에 물건을 부분적으로 더 담을 여유가 있으면

12       물건 x를 (C - w)만큼만 L에 추가한다.

13       v = v + (C - w)만큼의 x의 가치

     }

14 return L, v

---

line1 : 단위 무게 계산에 O(n) 시간 소요

line2 :  단위당 가치에 대해 내림차순 정렬에 O(nlogn) 소요

 

line5 ~ 10 : 물건 n개 중 다 담거나, n개보다는 적게 담길 테니 n. 루프 내부 수행은 O(1) 걸림 

둘을 곱하면 n * O(1)

lin11 ~ 13 각 O(1)씩 소요

 

 O(n) + O(nlogn) + n * O(1) + O(1) = O(nlogn)