배낭 문제란?
배경 = 물건 n개의 집합 S = {1, 2, 3, 4, ..., n}이 있고 물건 무게 W = {W1, W2, W3..., Wn},
물건을 팔았을 때의 가치(이윤) P = {P1, P2, P3, ..., Pn }가 있다고 하자.
조건 = W은 물건 무게 이므로 Wi > 0이어야 한다. P도 Pi > 0이어야 한다.
자신이 배낭에 물건을 가지고 가서 시장에서 판다고 가정하자
배낭에 넣을 수 있는 무게는 제한되었다. 최대 무게를 M이라고 하자
1 ~ n까지의 Wi * Xi ≤ M 이면서 (x= 물건의 개수)
1 ~ n 까지의 Pi * Xi 를 최대화하는 방향을 찾아야 한다.
• n개의 물건이 각각 1개씩 있고,
• 각 물건은 무게와 가치를 가지고 있으며,
• 배낭이 한정된 무게의 물건들을 담을 수 있을 때,
• 최대의 가치를 갖도록 배낭에 넣을 물건들을 정하는 문제
[2가지 문제]
문제 1) Xi의 값이 0 혹은 1만 허용되는 경우 = 0-1배낭 문제
0이면 그 물건을 가져갈 수 없다는 의미
1이면 그 물건을 가져가는 것이다.
즉, 물건을 가져갈 수도 이고 안가져갈 수도 있다는 것이다.
[ 0-1 배낭 문제 ]
• 부분 배낭 문제의 원형으로 물건을 통째로 배낭에 넣어야 한다.
• 동적 계획 알고리즘, 백트래킹 기법, 분기 한정 기법으로 해결
[특징]
- 효율적으로 해결하는 다항 시간의 알고리즘(시간 복잡도를 다항식으로 표현할 수 있는 알고리즘)은 아직 발견되지 않았다.
- O(n의 k 승) = polynomial complete 문제라고 하는데 이것을 아직 발견하지 못함
- NP문제 = Nondetermistic Polynomial 문제 = 다른 방법으로 푼다.
문제 2) Xi값이 0 ≤ Xi ≤ 1인 경우 = 부분 배낭 문제
Xi가 1/3이라면 물건 Xi를 1/3만 가져갈 수 있다는 것
[ 부분 배낭 (Fractional Knapsack) 문제 ]
• 물건을 부분적으로 담는 것을 허용
• 그리디 알고리즘으로 해결(간단하게 표현 가능)
아이디어
부분 배낭 문제에서는 물건을 부분적으로 배낭에 담을 수 있으므로, 최적해를 위해서 ‘욕심을 내어’ 단위 무게 당 가장 값나가는 물건을 배낭에 넣고, 계속해서 그 다음으로 값나가는 물건을 넣는다.
만일 물건을 ‘통째로’ 배낭에 넣을 수 없으면, 배낭에 넣을 수 있을 만큼만 물건을 부분적으로 배낭에 담는다.
만약 1개를 담지 못한다면 1/3만큼 넣을 수 있다는 것이다.
FractionalKnapsack
입력: n개의 물건, 각 물건의 무게와 가치, 배낭의 용량 C
출력: 배낭에 담은 물건 리스트 L과 배낭 속의 물건 가치의 합 v
1. 각 물건에 대해 단위 무게 당 가치를 계산한다.
ex) S = {( 백금-10개-6만원 ), ( 금-15개-5만원 ) , ( 은 - 25개 - 4천원 ) , (주석 - 80개 - 천원)}
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
시간복잡도
Line 1: n개의 물건 각각의 단위 무게 당 가치를 계산하는 데는 O(n) 시간 소요
Line 2: 물건의 단위 무게 당 가치에 대해서 정렬하기 위해 O(nlogn) 시간 소요
Line 5~10: while-루프의 수행은 n번을 넘지 않으며, 루프 내부의 수행은 O(1) 시간 소요
Line 11~14: 각각 O(1) 시간 소요
알고리즘의 시간 복잡도: O(n)+O(nlogn)+nxO(1)+O(1) = O(nlogn)