분할 가능한 배낭 문제.md

배낭 문제 (그리디 알고리즘)

문제

무게와 가치가 정해진 항목들의 집합이 주어졌을 때, 주어진 최대 무게 내에서 가치가 최대가 되도록 하는 항목의 수를 찾아라.

그리디 알고리즘은 분할 가능한 배낭 문제에서 항상 최적해를 제공한다.

시간 복잡도

최악: $O(nlog n)$

예시

배낭의 최대 무게 W = 60
value = [280, 100, 120, 120]  
weight = [40, 10, 20, 24]

Ratio(V/W) = 7,10,6,5
각 항목을 A,B,C,D라 하자.

먼저 항목들을 가치와 무게의 비율을 기준으로 내림차순으로 정렬한다. 
B는 배낭의 용량보다 작기 때문에 첫 번째로 선택된다. 다음으로, 남은 용량이 A의 무게보다 크기 때문에 A가 선택된다. 
배낭의 남은 용량이 C의 무게보다 작기 때문에 C는 전체 항목을 선택할 수 없다.
따라서 C는 (60-50)/20의 비율만큼 일부만 선택된다.
이제 배낭의 용량은 지정된 항목들의 무게와 동일해서 더 이상 항목을 선택할 수 없다.

선택된 물건들의 총 무게는 10+40+20*(10/20) = 60이다.

총 이익은 100+280+120*(10/20) = 380+60 = 440이다.

이것이 가장 적합한 선택이다. 다른 항목을 조합하여 더 많은 돈을 버는 것은 불가능하다.

구현

• C++
• Python
• C-Sharp

영상 URL

A CS50 video explaining the Greedy Algorithm