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)