[Algorithm] Fractional Knapsack

0. 문제

link: https://www.codetree.ai/missions/6/concepts/35/problems/fractional-knapsack/introduction

코드트리

knapsack 문제를 변형한 문제다. 다른 조건은 동일하다. 단, 보석을 쪼개어 담을 수 있다는 점이 차이점이다. 

보석을 쪼개어 담을 수 있을 때, 가장 가치가 높도록 보석을 담는 문제다. 

 

1. 풀이

 

이 문제는 knapsack 문제와 달리 동적계획법으로 접근할 수 없다. 보석을 어떻게 쪼개느냐에 따라 결과가 달라지기 때문이다. 

그리디 (Greedy) 알고리즘으로 접근하는 문제다. 

그리디 알고리즘이란, 현재 상황에서 최선을 계속 선택하며 문제를 풀어나가는 기법이다. 동적 계획법이 현재의 최선과 결과의 최선을 둘 다 보장함과는 달리, 그리디 알고리즘은 현재의 최선만을 보장한다. 그래서 자주 쓰이진 않지만, 다른 방법이 불가한 경우에 사용한다. 

 

보석을 쪼개어 담을 수 있으므로, 무게 당 가격이 가장 높은 보석을 담는 것이 최선일 것이다.

따라서 무게 당 가격으로 보석을 정렬한 뒤, 가장 높은 것을 통째로 (분할하지 않고) 담는다.

그러다 보석 하나가 들어갈 수 없을 만큼 무게가 남으면, 남은 보석 중 무게 당 가격이 가장 높은 보석을 쪼개어 담는다. 

 

2. 구현

 

m_n = input().split()
m, n = int(m_n[0]), int(m_n[1])
weight_price = [[0, 0, 0] for _ in range(m)]

for i in range(m):
    tmp = input()
    w_p = tmp.split()
    weight_price[i][0], weight_price[i][1] = int(w_p[0]), int(w_p[1])
    weight_price[i][2] = weight_price[i][1] / weight_price[i][0]

weight_price.sort(key=lambda x:x[2], reverse=True)

present_weight, present_price, idx, rest = 0, 0, 0, 0

for i in range(m):
    if present_weight + weight_price[i][0] <= n:
        present_weight += weight_price[i][0]
        present_price += weight_price[i][1]
        idx += 1
    else:
        break

rest = n - present_weight

if rest == 0 or idx == m:
    print(f'{present_price:.3f}')

elif idx < m:
    present_price += rest * weight_price[idx][2]
    print(f'{present_price:.3f}')

 

weight_price 배열에 무게, 가격, 무게 당 가격을 모두 담은 뒤, 무게 당 가격으로 정렬한다.

이후 n (가방 용량) 보다 작을 때까지 담을 수 있는 보석을 담고, 남는 무게는 남은 보석 중 가장 무게 당 가격이 높은 보석을 쪼개어 담는다.