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)