So I made a version for the 0/1 knapsack problem myself (using matrix dynamic programming algorithm). Given a list of items with name, value, and weight, my function computes correctly the optimal value with total weight <= allowed weight.
I don't know if my code is clean and pythonic enough, I would greatly appreciate it if you give me some comments, thanks.
def knapsack(W, items):
"""
Given a list of items with name, value and weight.
Return the optimal value with total weight <= allowed weight and
list of picked items.
"""
n = len(items)
k = [[0 for x in range(W+1)] for x in range(n+1)]
for i in range(n+1):
for w in range(W+1):
if i == 0 or w == 0:
k[i][w] = 0
elif items[i-1][2] <= w:
k[i][w] = max(items[i-1][1] + k[i-1][w-items[i-1][2]], k[i-1][w])
else:
k[i][w] = k[i-1][w]
picked = []
set_trace(k, n, W, items, picked)
return k[n][W], picked
# find which item are picked
def set_trace(k, n, W, items, picked):
for i in range(n, 0, -1):
if k[i][W] != k[i-1][W]:
picked.append(items[i-1])
set_trace(k, i-1, W-items[i-1][2], items, picked)
break
if __name__ == '__main__':
items = [('A', 1, 1), ('B', 4, 3), ('C', 5, 4), ('D', 7, 5)]
max_value, picked = knapsack(7, items)
print("Maximum value:", max_value)
print("Name", "Value", "Weight")
for item in reversed(picked):
print(item[0], ' '*2, item[1], ' '*3, item[2])
Output:
Maximum value: 9
Name Value Weight
B 4 3
C 5 4