부분 배낭 문제

부분 배낭 문제

배낭(Knapsack) 문제는 n개의 물건이 있고, 각 물건이 무게와 가치를 가지고 있을 때, 최대의 가치를 갖도록 한정된 용량의 배낭에 넣을 물건들을 정하는 문제

원래 배낭 문제는 물건을 통째로 배낭에 넣어야 되지만, 부분 배낭(Fractional Knapsack) 문제는 물건을 부분적으로 담는 것이 허용된다.

• 즉, 물건이 분말과 같다고 생각하면 된다.

부분 배낭 문제에서는 물건을 부분적으로 배낭에 담을 수 있으므로, 최적해를 위해서 ’욕심을 내어’ 단위 무게당 가장 값나가는 물건을 배낭에 넣고 그 다음으로 값나가는 물건을 넣다가 ’통째로’ 물건을 넣을 수 없게 된다면, 부분적으로 배낭에 담는다.

Pseudo Code

입력: n개의 물건과 각 물건의 무게와 가치, 배낭의 용량 C
출력: 배낭에 담은 물건 리스트 L과 배낭에 담은 물건의 가치 합 v

1. 각 물건의 단위 무게당 가치를 계산한다.
2. 물건들을 단위 무게당 가치를 기준으로 내림차순으로 정렬하고, 정렬된 물건 리스트를 S라고 하자.
3. L=null, 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

• Line 1~2에서는 각 물건의 단위 무게당 가치를 계산하여, 이를 기준으로 물건들을 내림차순으로 정렬한다.
• Line 5~10의 while-루프를 통해서 다음으로 단위 무게당 값나가는 물건을 가져다 배낭에 담고, 만일 가져온 물건을 배낭에 담을 경우 배낭의 용량이 초과되면(즉, while-루프의 조건이 ‘거짓’이 되면) 가져온 물건을 ‘통째로’ 담을 수 없게 되어 루프를 종료한다.
• Line 11에서는 현재까지 배낭에 담은 물건들의 무게 w가 배낭의 용량 C보다 작으면 (즉, if-조건이 ‘참’이면) line 12~13에서 해당 물건을 (C-w)만큼만 부분적으로 배낭에 담고, (C-w)만큼의 x의 가치만큼 v를 증가시킨다.
• Line 14에서 최종적으로 배낭에 담긴 물건들의 리스트 L과 배낭에 담긴 물건들의 가치의 합 v를 리턴한다.

예제

• 배낭의 최대 용량 40g

• 단위 무게(순서대로): $[1000,60000,4000,50000]$

1. 우선 단위 무게당 가격이 가장 높은 백금을 넣는다.
   1. 그렇다면, 배낭의 최대 용량은 30g, 가치는 60만원이 된다.
2. 그렇다면 그다음으로 가치가 높은 금을 넣는다.
   1. 그렇다면, 배낭의 최대 용량은 15g, 가치는 135만원이 된다.
3. 그 다음으로 가치가 높은 은을 넣지만 전부 넣지 못하므로 while 루프를 탈출한다.
   1. 그 다음으로 남은 15g만큼 은을 넣고, 4000*15 만큼 가치를 추가한다.

시간복잡도

알고리즘의 시간 복잡도를 살펴보면, line 1에서 n개의 물건 각각 단위 무게당 가치를 계산하는 데는 $O(n)$ 시간 걸리고, line 2에서 물건의 단위 무게당 가치에 대해서는 내림차순으로 정렬하기 위해 $O(nlogn)$ 시간이 걸린다. 또한 루프 내부의 수행은 $O(1)$ 시간이 걸리므로 따라서 $O(nlogn)$ 시간이 소요되게 된다.