[DP] [Algorithm] Fractional Knapsack Algorithm

https://pongdangstory.tistory.com/487

    이전 포스팅에서, Unfractional knapsack problem을 다루었다. 이번에는 가방에 물건을 담을 때, 물건의 일부를 담는 경우는 어떠할까? 믹서기 같은 물건의 경우, 믹서기를 쪼개면 그 기능을 다하지 못하기 때문에 쪼갤 수 없는 반면에, 초콜릿이라고 한다면, 초콜릿은 소분해서 담을 수 있고 그 가치도 그 소분한 가치만큼에 해당하기 때문에 쪼갤 수 있다. 이 경우 그리디 알고리즘의 접근법으로 비교적 간단히 풀 수 있다. 

   이전의 input과 동일하게 문제가 주어졌다고 가정하자. K는 가방에 담을 수 있는 최대 무게 상한선이다. 즉, 물건이든, 물건의 부분이든 이 K kg의 무게를 넘을 수 없다. stuff_array는 다음과 같다. stuff_array[i][0]은 i물건의 무게이고, stuff_array[i][1]는 이 물건의 가치이다. 

K = 7, stuff_array = [(6,13), (4,8), (3,6), (5,12)]

Weight	6	4	3	5
Value	13	8	6	12
Weight/Value	0.46...	0.5	0.5	0.41...

탐욕적 알고리즘으로 접근하는 부분은, 단위 무게별 가치가 높은 물품을 우선적으로 가방에 담는 것이다. 위의 예시 문제에서는 2,3번의 물건의 1kg당 가치가 가장 높으므로, 이들을 우선적으로 담게 된다. 이런 우선순위로 물건을 담다가, 물건의 전체를 모두 담을 수 없고 일부만을 담을 경우에는 남은 부분에 해당하는 만큼만 후보군에서 선정해서 가방에 담게 된다. 

이에 해당하는 코드는 다음과 같다. 

#tuple의 첫번째 원소를 단위 무게당 가치값으로 저장, 두번째 원소는 물건의 무게, 세번째 원소는 물건의 가치

for i in range(len(stuff_array)):
    temp = stuff_array[i][0]/stuff_array[i][1]
    candi.append((temp, *stuff_array[i]))

# 단위 무게당 가치를 기준으로 내림차순으로 정렬
candi.sort(key=lambda x:x[0], reverse=True) 

answer = 0 

for i in range(len(candi)):
    
    if K ==0:
        break
    
    if candi[i][1] <= K:
        answer += candi[i][0]
        K -= candi[i][1]
        
    else: 
        answer += candi[i][0]*K
        K = 0