## Lekcja – – Pakowanie plecaka – metoda naiwna (brute force)

```def backpack_brute_force_1(total_weight, weights, values, selected, i):

if i == len(selected):
v = sum(values[p] for p in range(len(selected)) if selected[p]==1)
w = sum(weights[p] for p in range(len(selected)) if selected[p]==1)
print(selected, 'value = ', v, 'weight = ', w)
return -1 if w > total_weight else v

# don't take
selected[i] = 0
v0 = backpack_brute_force_1(total_weight, weights, values, selected, i+1)
# take
selected[i] = 1
v1 = backpack_brute_force_1(total_weight, weights, values, selected, i+1)

return max(v0, v1)

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

print(values)
print(weights)
selected = [0,0,0,0,0]
print(backpack_brute_force_1(total_weight, weights, values, selected, 0))

def backpack_brute_force_2(total_weight, weights, values, n, selected):

if n  == 0 or total_weight == 0:
return 0, selected

if (weights[n-1] > total_weight):
return backpack_brute_force_2(total_weight, weights, values, n-1, selected)
else:
selected_1 = selected.copy()
case_1_weight, selected_1 = backpack_brute_force_2(total_weight, weights, values, n-1, selected_1)

selected_2 = selected.copy()
selected_2[n-1] = 1
delta, selected_2  =  backpack_brute_force_2(total_weight-weights[n-1], weights, values, n-1, selected_2)
case_2_weight = values[n-1] + delta

if case_1_weight > case_2_weight:
return case_1_weight, selected_1
else:
return case_2_weight, selected_2

print(values)
print(weights)
selected = [0,0,0,0,0]
n = len(values)
print (backpack_brute_force_2(total_weight, weights, values, n, selected))

```

## Rozwiązanie

```def coin_change_naive(coins, value):

# if the value is 0, we don't have anything to do
if value == 0:
return []

# we will return  ret_tab_coins, currently we don't know if there is a solution,
# so we are going to return None
ret_tab_coins = None

# make simulation for every coin
for c in coins:

# to find a solution the coin needs to be smaller or equal to the value
if value >= c:
# we recursively check the problem with decreased value
ret_tab_tmp = coin_change_naive(coins, value - c)
# if solution for the smaller number was found
if ret_tab_tmp != None:
# we add also the currently considered coin
ret_tab_tmp.append(c)

# if no solution till now
if ret_tab_coins == None:
# save the current solution
ret_tab_coins = ret_tab_tmp
# else - check if the new solution is better than the old, if yes - take it
elif len(ret_tab_tmp) < len(ret_tab_coins):
ret_tab_coins = ret_tab_tmp

return ret_tab_coins

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

```