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