[Algorithm] Knapsack algorithm - Greedy 사용

 

지난번에 가방 문제가 무엇인지 알아보고 0/1 knapsack problem을 DP 로 해결하는 방법을 알아보았다. 이번에는 그 글을 이어서 fractional knapsack problem에 대해 알아보겠다. 

0/1 knapsack problem 과 다른 상황이니 주의하고 글을 읽기 바란다. 0-1 knapsack 은 greedy algorithm으로 풀 수 없다.

2023.06.07 - [Computer Science/Data structure & Algorithm] - [Algorithm] Knapsack algorithm (배낭 알고리즘) - DP 이용

[Algorithm] Knapsack algorithm (배낭 알고리즘) - DP 이용

 

Fractional Knapsack Problem

문제상황

당신은 크기가 W인 가방과  n개의 물건을 가지고 있다.  각 물건은 하나씩 존재한다. 
각 물건 i는 크기 Wi와 가치 Vi를 가지고 있다. 
당신이 이 가방에 물건을 담으려고 할 때,  가방에 담을 수 있는 물건들의 가치의 합이 최대가 되도록 하려면 어떤 물건들을 선택해야할까?

문제 상황은 같으나 한 가지가 다르다. 물건을 이진선택 ( 선택과 선택하지 않음) 하는 것이 아니라, 물건의 일부도 넣을 수도 있다. 

ex) 20Kg 물건을 10Kg만 떼서 가방에 넣기 가능

 

해결방안

접근은 간단하다. 가치/무게의 비율이 높은 순으로 넣어주면 된다 

만약, 물품의 무게가 무게의 최대치보다 크다면 (물품의 비율) * (최대치까지 남은 무게) 를 구해 답에 더해주면 된다. ( 예제로 보면 바로 이해가 될 것이다. )

예제 풀이

item	value	weight
1	50	5
2	60	10
3	140	20

가방에 담을 수 있는 총 무게는 30이라고 하자.

1. 가치 / 무게의 비율을 구한다.

item	V	W	V / W
1	50	5	10
2	60	10	6
3	140	20	7

 

2.  V/W가 높은 것부터 차례대로 가방에 넣는다. 

V/W가 가장 높은 것은 1번이기 때문에 가방에 1번을 넣는다. 가방에 30까지 넣을 수 있기 때문에 5를 모두 넣어준다. 
그 뒤 V/W가 높은 것은 3번이다. 3번 20을 넣어준다. 

이러면 가방에 5만큼 공간이 남는다. 아이템 2번을 넣으려고 했지만, item 2번은 10이라서 가방에 전부 들어가지 않는다. 우리는 그럼 넣을 수 있는 만큼만 뜯어서 넣는다. item 2번은 5만큼 넣는다.

 

정리하면, 1번 5, 3번 20, 2번 5 를 넣어 총 30이 채워졌다. 가방에 들어간 물품의 가치는 1번 50, 3번 140, 2번 30(절반만 넣음)으로 총 220이다. 

 

Greedy 방식은 상대적으로 DP 보다 어렵지 않기 때문에 간단하게 마무리하려고 한다.