Kursy Online

Lekcja – Pakowanie plecaka – metoda zachłanna (greedy)

def backpack_greedy(weights, values, total_weight):

    data = []
    for i in range(len(weights)):
        data.append({
            "v": values[i],
            "w": weights[i],
            "cost": float(values[i])/float(weights[i])
        })

    data = sorted(data, key=lambda x: x['cost'], reverse=True)
    print(f'DEBUG: {data}')

    remain = total_weight
    result = 0
    result_list = []
    i = 0

    while i < len(data):
        if (data[i]['w'] <= remain):
            remain -= data[i]['w']
            result += data[i]['v']
            result_list.append(data[i])
            print(f"DEBUG: adding {data[i]} - total value = {result} remaining space = {remain}")
        i += 1

    return result, result_list


values = [60, 100, 120, 30, 600]
weights = [10, 20, 30, 5, 20]
total_weight = 50

print(backpack_greedy(weights, values, total_weight))

Rozwiązanie

def coin_change_greedy(coins, value):

    tab_result = []

    while value > 0:
        
        highest_coin = 0
        for c in coins:
            if c <= value and c > highest_coin:
                highest_coin = c

        value -= highest_coin
        tab_result.append(highest_coin)

    return tab_result


coins = [1,2,5,10,20]
for value in range(30):
    change = coin_change_greedy(coins, value)
    print(value, change)