Greedy Algorithm - Fractional Knapsack Problem

- Fractional  Knapsack 

n개의 물건과 1개의 배낭이 있다 
물건 i의 무게는 W(i), 이익은 P(i), 배낭용량은 M까지 가능하다 
물건들을 배낭에 섞어서 넣되, 무게가 M을 넘지 않으면서
이윤이 최대가 되도록 물건을 담는 방법? (물건을 잘라서 담을 수 있다)

 

 

 

예시 ) 

이익, 무게 등 무엇을 기준으로 잡고 greedy algorithm을 수행할지에 따라 결과가 다르다.
그러나 Fractional Knapsack 문제에서는 물건의 무게당 이익이 큰것을 기준으로 잡고  Algorithm을 짜면 항상 최적의 이익을 얻을 수 있다. 
단, 단위 무게 당 이익이 큰 순서대로 정렬이 되어있어야만 하며,  정렬이 되어있다면  Time complexity는 O(n)이 된다

 

그러므로 최대 이익은 31.5가 된다

 

 

구현 방법 )

✔ Greedy Algorithm을 사용하여 풀어준다. 

< Greedy Algorithm이란? > 

결정을 해 야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 solution으로 선택함으로써  
최종 solution에 도달하는 Algorithm이다. 
그 당시에는 최적의 solution을 선택하나 최종적인 solution이 최적이라는 보장이 없다.  
보통 greedy choice property 와 optimal substructure property를 만족할때 사용하는 것이 좋다

- greedy choice property : 전의 선택이 후의 선택에 영향을 미치지 않는 경우 
- optimal substructure property : 문제 전체에 대한 최적 solution이 부분 문제에 대해서도 최적 solution일 때 

 

 

< Fractional Knapsack Function  구현 순서> 

1. 무게 당 값어치가 큰 물건 순서대로 정렬해준다 → Sortitem 
2. list의 앞에서 차례로 가방에 담을 수 있는 물건들을 담아준다  
   ( 가방의 용량보다 작은 물건들을 담아준다 )  
   → 즉, M-w(i) > 0이면 계속해서 반복  
3. M이 남았다면, 안담은 item의 부분만 잘라서 담아준다. 
   → 남은 물건 i는 남은 무게 / w(i) 만큼만 담아주면 된다  

 

 

- python code

def Sortitem(iteminfo):
    for i in range(len(iteminfo)):
        iteminfo[i].append(round(iteminfo[i][1]/iteminfo[i][0],2)) # price/weight값을 저장
    iteminfo.sort(key=lambda x:x[2]) # price/weight값이 큰 순서대로 정렬
    iteminfo.reverse()



def Factional_Knapsack(iteminfo,M):
    Sortitem(iteminfo)
    i=0
    price=0
    while (M-iteminfo[i][0])>=0:
        print(i)
        M-=iteminfo[i][0]
        price+=iteminfo[i][1]
        i+=1
        if i>=len(iteminfo): # 모든 item들을 다 담은 경우
            break
    # 남은 경우에 
    if M>0 and i<len(iteminfo):
        price+=iteminfo[i][1]*(round(M/iteminfo[i][0],2))
    return price

    
        
# Data input
itemlist=[]
n=int(input('물건 갯수?'))
M=int(input('배낭 용량? '))
for i in range(n):
    item= list(map(int,input('물건의 무게, 값어치를 차례로 입력').split()))
    itemlist.append(item)


print(Factional_Knapsack(itemlist,M))