def knapsack_dynamic(total_weight, weights, values): n = len(values) tab = [[0 for i in range(total_weight + 1)] for j in range(n + 1)] tab_lists = [[ [] for i in range(total_weight + 1)] for j in range(n + 1)] for obj_row in range(n + 1): for w in range(total_weight + 1): if obj_row == 0 or w == 0: tab[obj_row][w] = 0 tab_lists[obj_row][w] = [] # The total weight after including object [i] should not exceed the weight limit. elif weights[obj_row-1] <= w: # The profit after including object [i] should be greater as compared to when the object is not included. if values[obj_row-1] + tab[obj_row-1][w-weights[obj_row-1]] > tab[obj_row-1][w]: tab[obj_row][w] = values[obj_row-1] + tab[obj_row-1][w-weights[obj_row-1]] tab_lists[obj_row][w] = tab_lists[obj_row-1][w-weights[obj_row-1]].copy() tab_lists[obj_row][w].append(values[obj_row-1]) else: tab[obj_row][w] = tab[obj_row-1][w] tab_lists[obj_row][w] = tab_lists[obj_row-1][w].copy() else: tab[obj_row][w] = tab[obj_row-1][w] tab_lists[obj_row][w] = tab_lists[obj_row-1][w].copy() return tab[n][total_weight], tab_lists[n][total_weight] values = [6, 10, 12, 3, 60] weights = [1, 2, 3, 5, 2] total_weight = 5 print(knapsack_dynamic(total_weight, weights, values)) values = [60, 100, 120, 30, 600] weights = [10, 20, 30, 5, 20] total_weight = 50 print(knapsack_dynamic(total_weight, weights, values))
def coin_change_dynamic(coins, value): tab_numbr = [[ 0 for v in range(value + 1)] for c in range(len(coins) + 1)] tab_coins = [[ [] for v in range(value + 1)] for c in range(len(coins) + 1)] for i in range(1, value + 1): tab_numbr[0][i] = float('inf') # by default change is impossible # for each row of the constructed table for coin_row_idx in range(1, len(coins)+1): current_coin = coins[coin_row_idx - 1] for value_limited in range(1, value + 1): # current_coin is too big - we need to take value from the previous row if current_coin > value_limited: tab_numbr[coin_row_idx][value_limited] = tab_numbr[coin_row_idx - 1][value_limited] tab_coins[coin_row_idx][value_limited] = tab_coins[coin_row_idx-1][value_limited].copy() # yes - we could take this coin else: # the value after adding this coin will be worse (higher) than in the previous row # so copy data from the previous row if tab_numbr[coin_row_idx - 1][value_limited] <= 1 + tab_numbr[coin_row_idx][value_limited - current_coin]: tab_numbr[coin_row_idx][value_limited] = tab_numbr[coin_row_idx - 1][value_limited] tab_coins[coin_row_idx][value_limited] = tab_coins[coin_row_idx - 1][value_limited].copy() # the value after adding this coin will be better (lower) than in the previus row # so take this coin else: tab_numbr[coin_row_idx][value_limited] = 1 + tab_numbr[coin_row_idx][value_limited - current_coin] tab_coins[coin_row_idx][value_limited] = tab_coins[coin_row_idx][value_limited - current_coin].copy() tab_coins[coin_row_idx][value_limited].append(current_coin) for row in tab_numbr: print(row) return tab_numbr[-1][-1], tab_coins[-1][-1] coins = [1,2,5,10,20] value = 7 change = coin_change_dynamic(coins, value) print(value, change) # coins = [1,2,5,10,20] # for value in range(30): # change = coin_change_dynamic(coins, value) # print(value, change)