Knapsack Problem

배낭 문제 (Knapsack problem)

문제의 정의

• n 개의 물체와 배낭 하나가 주어진다.
• 물체i 는 그 무게 wi 와 이익 pi를 갖고,
  가방은 무게 M 을 가진다.
• 물체i 의 일부인 xi는 0 <= xi <= 1 을 만족하며
  이것이 배낭 안에 담길 시 pi * xi 의 이익을 얻는다.

여기서 문제 :
우리의 목적은 총 이익을 최대로 만들면서
배낭을 채우는 방법을 구하는 것이다.

해답은 xi 들의 집합이다. (몇 개를 담을지)

**예시

n = 3,
M = 30,
(p1, p2, p3) = (30, 25, 15),
(w1, w2, w3) = (20, 15, 12) 이라 할 때

(x1, x2, x3) 는?

해결 전략

각 단계마다 무게 당 이익이 가장 큰 물체를 택한다.
pi/wi 의 비율 순으로 정렬한다.

예시의 문제를 풀어보자.

이익/무게 비율을 r 로 둔다.

(r1, r2, r3) = (1.5, 1.66, 1.25)
이를 높은 순으로 정렬하면

r2, r1, r3 이므로
r2 물체 2개를 담으면 이익 50에 무게 30으로 최대 이익을 볼 수 있다.