Classic dynamic programming question. I have a 2 video series explaining
the construction of the table manually, then coding the algorithm previously done by hand, in python.
In the above case, the total represents the weight of a backpack and the item weights are analogous to coins, but it's the same rational.
coins = [1,2,5] total = 5 # Dynamic programming solution def ways_to_make_change(coins_list, total_amount): table = [[0 for x in range(total_amount+1)] for y in range(len(coins_list))] # First column will be ones since there's 1 way to make zero change for all coins for row in table: row = 1 # First iterate over the coins then iterate over the totals for idx_c, coin in enumerate(coins_list): for idx_a, amount in enumerate(range(total_amount+1)): if coin <= amount: table[idx_c][idx_a] = table[idx_c - 1][idx_a] + table[idx_c][amount - coin] continue else: table[idx_c][idx_a] = table[idx_c - 1][idx_a] continue return max([x for sublist in table for x in sublist]) assert(ways_to_make_change(coins, total)) == 4