## 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)

```