[Algorithm] 부분 배낭 문제

💡배낭 문제 

• n개의 물건이 있고, 각 물건은 무게와 가치를 가지고 있으며, 배낭이 한정된 무게의 물건들을 담을 수 있을 때, 최대의 가치를 갖도록 배낭에 넣을 물건들을 정하는 문제

💡부분 배낭 문제

• 물건을 부분적으로 (쪼개서) 담는 것을 허용
• 최적해를 위해서 '욕심내어' 단위 무게 당 가장 값나가는 물건을 배낭에 넣고, 계속해서 그 다음으로 값나가는 물건을 넣는다.
• 만약, 그 다음으로 값나가는 물건을 '통째로' 배낭에 넣을 수 없게되면, 배낭에 넣을 수 있을 만큼만 물건을 부분적으로 배낭에 담는다.

 

💡의사코드

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

• 1. 각 물건에 대해 단위 무게당 가치를 계산
  2. 물건들을 단위 무게 당 가치를 기준으로 내림차순으로 정렬하고, 정렬된 물건 리스트를 S
  3. L = ∅, w = 0, v = 0 ( w = 배낭에 담긴 물건들의 무게의 합 )
  4. S에서 단위무게당 가치가 가장 큰 물건 x를 가져온다.
  // 배낭에 물건을 통째로 담기 (물건을 통째로 담을 수 없게 되면 루프를 종료)
  5. whild(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){ //배낭에 물건을 부분적으로 담을 여유가 있는 지 확인 ( 현재까지 배낭에 담은 물건들의 무게 w가 배낭의 용량 C보다 작으면, )
  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) + n x O(1) + O(1) = O(nlogn) (Sorting이 가장 큰 영향)

 

➰응용

• 0-1 배낭 문제는 최소의 비용으로 자원을 할당하는 문제로, 조합론, 계산이론, 암호학, 응용수학 분야의 기본문제
• 응용사례 : '버리는 부분 최소화시키는' 원자재 자르기
• 자산 투자 및 금융 포트폴리오에서의 최선의 선택
• Merdle - Hellman 배낭 암호 시스템의 키 생성

 

---

Reference 

서울과학기술대학교 컴퓨터공학과 알고리즘 수업