탐욕 알고리즘

greedy algorithm

• 최적의 해에 가까운 값을 귀하기 위해 사용
• 여러 경우 하나를 결정행 할 때마다 매순간 최적이라고 생각되는 경우를 선택

탐욕 알고리즘 문제

동전문제

coin_list = [1,10,100,500,50]

def greedy_coin(cost, coin_list):
	total_coin =0
    details = list()
    coin_list.sort(reverse = True)
    for coin in coin_list:
    	numberOfCoin = cost // coin
        total_coin += numberOfCoin
        cost -= numberOfCoin * coin
        details.append([coin, numberOfCoin])
        
     return total_coin, details
     

부문 배낭 문제

data_list [(10,10), (5,2) , (15,20), (25,8), (30,2)]

def get_max_value(data_list, capacity):
    data_list = sorted(data_list, key=lambda x: x[1] / x[0], reverse=True)
    total_value = 0
    details = list()
    
    for data in data_list:
        if capacity - data[0] >= 0:
            capacity -= data[0]
            total_value += data[1]
            details.append([data[0], data[1], 1])
        else:
            fraction = capacity / data[0]
            total_value += data[1] * fraction
            details.append([data[0], data[1], fraction])
            break
    return total_value, details