탐욕 알고리즘

모든 경우의 수를 놓고 최적의 경우를 고른다기보다는 각 단계에서 최적의 경우를 고르는 전략임

그렇기 때문에 최적의 경우가 아닌 결과가 도출될 수 있음 (탐욕이라는 말이 정말 적절하다...)

탐욕 알고리즘을 사용하면 19의 결과가 도출되겠지만, 실제로 최적의 결과는 15다.

문제1: 동전 문제

지불해야 하는 값이 4720원 일 때 1원 50원 100원, 500원 동전으로 동전의 수가 가장 적게 지불하시오.

coin_list = [500, 100, 50, 1]

def min_coin_count(value, coin_list):
    total_coin_count = 0
    details = list()
    coin_list.sort(reverse=True)
    for coin in coin_list:
        coin_num = value // coin
        total_coin_count += coin_num
        value -= coin_num * coin
        details.append([coin, coin_num])
    return total_coin_count, details
    
min_coin_count(4720, coin_list)

// (31, [[500, 9], [100, 2], [50, 0], [1, 20]])

 

문제2: 부분 배낭 문제 (Fractional Knapsack Problem)

무게 제한이 k인 배낭에 최대 가치를 가지도록 물건을 넣으시오. (단, 물건은 쪼갤 수 있음.)

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
    
get_max_value(data_list, 30)
// (24.5, [[10, 10, 1], [15, 12, 1], [20, 10, 0.25]])