그리디 - 몸풀기 문제

### 문제 80 거스름돈 주기

상점에세 계산을 마치고 거스름돈을 돌려받아야
거스름돈을 최소한의 화폐 수로 받고 싶음
거스름돈 amount 가 있을 때 화폐 단위 [1,10,50,100]을 최소한으로 사용한 화폐 리스트 반환

def solution(amount):
	denominations=[1,10,50,100]
    denominations.sort(reverse=True)
    
    change=[]
    for coin in denominations:
    	while amount>=coin:
        	change.append(coin)
            amount-=coin
    return change

### 문제 81 부분 배낭 문제

무게와 가치가 있는 짐 items와 배낭 weight_limit이 주어질 때 부분 배낭 문제 풀기

def calculate_unit_value (items):
	for item in items:
    	item.append(item[1]/item[0])
    return items
    
def sort_by_unit_value (items):
	items.sort(key=lambda x:x[2], reverse=True)
    return items

def knapsack(items,weight_limit):
	total_value=0
    remaining_weight=weight_limit
    
    for item in items:
    	if item[0]<=remaining_weight:
        	total_value+=item[1]
            remaining_weight-=item[0]
            
        else:
        	fraction=remaining_weight/item[0]
            total_value+=item[1]*fraction
    return total_value
    
def solution(items,weight_limit):
	items=calculate_unit_weights(items)
	items=sort_by_unit_value(items)
    
    return knapsack(items,weight_limits)