그리디 알고리즘 - 부분 배낭 문제

부분 배낭 문제

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

그렇다면 부분 배낭 문제는 무엇이 다른 가?

배낭 문제에서는 물건을 통째로 넣어야 하는 것에 반해, 부분 배낭 문제는 물건을 부분적으로 담는 것이 허용된다. 

최적해를 위해 단위 무게당 가장 값나가는 물건을 배낭에 넣고, 다음 값나가는 물건을 넣는 중에 통째로 넣는 것이 불가능 하다면 두 번쨰로 값나가는 물건을 배낭에 넣을 수 있는 만큼 부분적으로 담는 것이다.

---

알고리즘 

FractionalKnapsack
입력: n개의 물건과 각 물건의 무게와 가치, 배낭의 용량 C
출력: 배낭에 담은 물건 리스트 L과 배낭에 담은 물건의 가치 합 v
각 물건의 단위 무게당 가치를 계산.
물건들을 단위 무게당 가치를 기준으로 내림차순으로 정렬, 정렬된 물건 리스트를 S라고 한다.
L=∅, w=0, v=0 
// L: 배낭에 담을 물건 리스트
// w: 배낭에 담긴 물건들의 무게의 합
// v: 배낭에 담긴 물건들의 가치의 합
S에서 단위 무게당 가치가 가장 큰 물건 x를 가져온다.
while((w + x의 무게)<=C){
  x를 L에 추가시킨다.
  w = w + x의 무게
  v = v + x의 가치
  x를 S에서 제거한다.
  S에서 단위 무게당 가치가 가장 큰 물건 x를 가져온다.
}
if ((C-w) > 0) { // 배낭에 물건을 부분적으로 더 담을 여유가 있으면
  물건 x를 (C-w)만큼만 L에 추가한다.
  v = v + (C-w)만큼의 x의 가치
}
return L, v

 

EX) 4개의 금속 분말, 배낭 최대 용량은 40g

 

• Line 4 : 단위 무게당 가치, 주석 1천원, 백금 6만원, 은 4천원, 금 5만원
• Line 5 : S = {백금,금,은,주석}
• Line 6 : L=∅, w=0, v=0로 각각 초기화한다.
• Line 7 : S에서 단위 무게당 가장 큰 물건인 백금을 x로서 가져온다.
• Line 8 : w + x의 무게 = 10g < C = 40g 으로 while-문 조건을 만족한다.
• Line 9 : 백금 x를 L에 추가, L = {백금}
• Line 10 : w = 0 + 10g = 10g
• Line 11 : v = 0 + 60만원 = 60만원
• Line 12 : S = {금,은,주석}
• Line 13 : S에서 금을 x로서 가져온다.
• Line 8 : w + x의 무게 = 10g + 15g < C = 40g, while-문 조건 만족
• Line 9 : L ={백금, 금}
• Line 10 : w = 10g + 15g = 25g
• Line 11 : v = 60만원 + 75만원 = 135만원
• Line 12 : S = {은,주석}
• Line 13 : S에서 은을 x로서 가져온다.
• Line 14 : w + x의 무게 = 25g + 25g = 50g > C = 40g, while-문 조건 만족X
• Line 15 : C-w = 40g - 25g = 15g > 0, if-문 조건 만족
• Line 16 : 물건 x인 은을 (C-w) = 15g만큼만 L에 추가, L = {백금,금,은}
• Line 17 : v = 135만원 + (C-w)만큼의 x의 가치 = 135만원 + 15X4천원 = 141만원
• Line 19 : L = {백금, 금, 은}, v = 141만원 반환

---

시간 복잡도

각각 n개의 물건 단위 무게당 가치를 계산하는 시간 : O(n)

내림차순 정렬 : O(nlogn)

while 루프 수행 : n번 넘지 않음

루프 내부 수행 : O(1)

Libe 14~17 : O(1) 

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

---

 부분 배낭 문제의 원형 = 0-1 배낭 문제 

-> 그리디 알고리즘으로 해결 불가하다

동적 계획 알고리즘, 백트레킹 기법, 분기 한정 기법으로 해결 가능 

-> 조합론, 계산이론, 암호학, 응용수학 분야에서 기본적인 문제로 다룸

'버리는 부분 최소화' 원자재 기르기, 자산투자 및 금용 포트폴리오에서의 최선의 선택, Merjle-hellman 배낭 암호 시스템 키 생성에 응요할 수 있다