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
1 Answer 1
Kudos for using list comprehensions. However picked = []; set_trace(k, n, W, items, picked) and picked.append(items[i-1]) doesn't feel as good.
One could expect set_trace to build the list and return it. Even better, would be to picked = list(set_trace(k, n, W, items)), meaning set_trace would be a generator (with a pretty terrible name).
In order to do so, you first have to come to the conclusion that the recursion is really not necessary. All you do, in that recursive call, is continue the iteration at the next step with a different W. And that's it, you break. You could have just replace these two lines with W -= items[i-1][2]. Doing so, you could replace the append with a yield and you have your generator:
def set_trace(k, n, W, items):
for i in range(n, 0, -1):
if k[i][W] != k[i-1][W]:
yield items[i-1]
W -= items[i-1][2]
this lets you define picked = list(set_trace(k, n, W, items)).
However, n is len(items) so you might as well not pass it as a parameter and compute it at the beginning of the function.
You can also get much better readability by improving your naming. I understand that you named your variables based of the math theory that this problem relly on, but single letter variable names are a poor choice.
Same for using a simple tuple to store your items: it doesn't convey meaning. Use a namedtuple instead.
Last thing, since you are skipping the first row and first column of k, you can use slices and the enumerate builtin to avoid using so much brackets; you can also improve set_trace in such a way by using zip to create pairwise values of potential weights:
from collections import namedtuple
Item = namedtuple('Item', 'name value weight')
def knapsack(allowed_weight, 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.
"""
k = [
[0 for x in range(allowed_weight + 1)]
for x in range(len(items) + 1)
]
for next_idx, (item, weights) in enumerate(zip(items, k), 1):
for w, current_weight in enumerate(weights[1:], 1):
if item.weight <= w:
k[next_idx][w] = max(
item.value + weights[w - item.weight],
current_weight
)
else:
k[next_idx][w] = current_weight
return k[-1][-1], list(fetch_items(k, allowed_weight, items))
# find which item are picked
def fetch_items(k, allowed_weight, items):
for item, weights_p, weights_n in zip(items[::-1], k[-2::-1], k[::-1]):
if weights_n[allowed_weight] != weights_p[allowed_weight]:
yield item
allowed_weight -= item.weight
if __name__ == '__main__':
items = [
Item('A', 1, 1),
Item('B', 4, 3),
Item('C', 5, 4),
Item('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.name, ' '*2, item.value, ' '*3, item.weight)