1) Fractional Knapsack Problem

Fractional Knapsack Problem

 

 

Fractional Knapsack Problem

- Greedy 

 

0-1 Knapsack Problem

- Dynamic 

- Backtracking

- Branch and Bound

 

Greedy 탐욕 알고리즘

greedy는 '욕심많은'이라는 뜻이다.

greedy algorithm이란 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫒는 방식이다.

 

 

배낭문제

배낭문제는 최소 비용으로 자원을 할당하는 문제이다.

조합론, 계산이론, 암호학, 응용수학 분야에서 기초적인 문제로 다뤄진다.

 

배낭문제 응용사례

- 버리는 부분을 최소화시키는 원자재 자르기

- 자산투자 및 금융 포트폴리오에서 최선의 선택

- Merkle-Hellman 배낭 암호 시스템의 키 생성

 

 

Fractional Knapsack Problem

물건들을 배낭에 섞어서 넣되, 무게가 M을 넘지 않으면서 이윤이 최대가 되도록 배낭에 물건 넣기

 

- n개의 물건과 1개의 배낭이 있다

- 각 물건 i의 무개는 wi, 값어치는 pi, 배낭의 최대 무게는 M이라고 하자

- 물건 i를 xi 만큼 배낭에 넣는다면 이윤은 pi * xi가 된다.

 

=> optimal 최적화 문제로 풀어보자.

 

 

Fractional Knapsack Problem example

n = 3, M = 20

물건 (n1, n2, n3)

값어치 (p1, p2, p3) = (25, 24, 15)

무게 (w1, w2, w3) = (18, 15, 10)

 

값어치, 무게의 영향으로 4개의 가능한 해가 존재한다.

 

 

1) Start with an arbitrary one, 임의의 하나의 값 선택하기

 

물건 (n1, n2, n3) = (1/2, 1/3, 1/4) 

값어치 (p1, p2, p3) = (25, 24, 15)

무게 (w1, w2, w3) = (18, 15, 10)

 

total 무게 ∑ wi*ni : 18 * 1/2 + 15 * 1/3 + 10 * 1/4 = 16.5

total 이윤 ∑ pi*ni : 25 * 1/2 + 24 * 1/3 + 15 *  1/4 = 24.25

 

 

2) Start with the largest profit, 최고 이윤을 갖도록 자르기

 

물건 (n1, n2, n3) = (1, 2/15, 0) 

값어치 (p1, p2, p3) = (25, 24, 15)  ==> 가장 높은 이윤에 가장 큰 가중치 값 부여하기 = 물건 자르기

무게 (w1, w2, w3) = (18, 15, 10) ==> 최대 무게를 넘지 않도록 조정하기

 

total 무게 ∑ wi*ni : 18 * 1 + 15 * 2/15 + 10 * 0 = 20

total 이윤 ∑ pi*ni : 25 * 1 + 24 * 2/15 + 15 * 0 = 28.2

 

 

3) Strart with the smallest weight, 가장 작은 무게를 갖도록 자르기

 

물건 (n1, n2, n3) = (0, 2/3, 1) 

값어치 (p1, p2, p3) = (25, 24, 15)  

무게 (w1, w2, w3) = (18, 15, 10) ==> 무게를 최소화시키기 위해 무게가 가장 작은 물건을 크게 자르기

 

total 무게 ∑ wi*ni : 18 * 0 + 15 * 2/3 + 10 * 1 = 20

total 이윤 ∑ pi*ni : 25 * 0 + 24 * 2/3 + 15 * 1 = 31

 

 

4) 단위 무게당 profit이 큰 것

=> ★ optimal 한 방식이다★

 

p1/w1 > p2/w2 > p3/w3 >... > pn/wn = (24/15 > 15/10 > 25/18)

=> 단위 무게당 이윤이 큰 물건은 물건 2, 물건 3, 물건 1 오름차순이다.

 

물건 (n1, n2, n3) = (0, 1, 1/2) => 물건 2, 물건 3, 물건 1 순서대로 무게가 넘지 않도록 크게 자른다. 

값어치 (p1, p2, p3) = (25, 24, 15)  

무게 (w1, w2, w3) = (18, 15, 10)

 

total 무게 ∑ wi*ni : 18 * 0 + 15 * 1 + 10 * 1/2 = 20

total 이윤 ∑ pi*ni : 25 * 0 + 24 * 1 + 15 * 1/2 = 31.5  =>  가장 최대 이윤을 갖게 된다.

 

 

Fractional Knapsack Time Complexity

정렬이 되어있는 경우 : O(n)

정렬이 되어 있지 않은 경우 : O(nlogn)