• 상남자특) 일단 가봄
• 상남자특) 뒤돌아보지 않음
  
  

Knapsack problem

• $S=\{item_1,\;item_2,\;\cdots,\;item_n\}$: 물건들의 집합
• $w_i$: $item_i$의 무게
• $P_i$: $item_i$의 값
• $W$: 배낭이 수용 가능한 총 무게

크게 다음의 두 종류가 있다.

• 0-1 Knapsack problem
  물건을 쪼갤 수 없는 경우
• fractional knapsack problem
  물건을 쪼개서 담을 수 있는 경우
  
  

0-1 knapsack problem

• 완전 탐색으로 $S$의 모든 부분집합 $s$를 구한다.
• $s$의 총 무게가 $W$를 초과하면 버린다.
• 물건 개수 $n$에 대해 $O(2^n)$의 시간 복잡도를 갖는다.

다음을 가정한다.

값이 비싼 물건부터 채우기

• 최적 해: $\{item_2,\;item_3\} \rightarrow w=20,\;p=14$
• 탐욕적 해: $\{item_1\} \rightarrow w=25,\;p=10$

가벼운 물건부터 채우기

• 최적 해: $\{item_2,\;item_3\} \rightarrow w=20,\; p=14$
• 탐욕적 해: $\{item_2,\;item_3\} \rightarrow w=20,\;p=14$

그러나 $P_1=15$라면 최적 해는 $\{item_1\}$이 되므로 성립하지 않게 된다.

무거운 물건부터 채우기

• 최적 해: $\{item_2,\;item_3\} \rightarrow w=20,\;p=14$
• 탐욕적 해: $\{item_1\} \rightarrow w=25,\;p=10$

결과적으로 correctness가 보장되지 않는다.

fractional knapsack

이건 당연히 가능
가성비(무게 당 가격)가 좋은 것부터 담다가 가방에 남은 무게에 맞춰 쪼개 담으면 된다.