How do you solve the 0/1 knapsack problem, and why is the loop order so important?
You keep a table of the best value you can get for each amount of space, and you fill it in one item at a time.
def max_value(weights, values, capacity):
best = [0] * (capacity + 1)
for weight, value in zip(weights, values):
for space in range(capacity, weight - 1, -1):
best[space] = max(best[space], best[space - weight] + value)
return best[capacity]
And why is the loop order so important? The space loop has to go backwards. That is what stops the same item being used more than once.
Here is the reason. When you are at a space of s, you read the entry for s minus the weight. If the loop went forwards then that entry would already have been updated for this item, so you would be adding the value of the item to a total that already included it. That would let you use the item twice, which is not allowed.
the item weight 2, value 3
the capacity 4
with the loop going backwards
the best for space 4 is 6, from two copies of the item
no wait, it is 3, because the space 2 entry was not yet
updated for this item
with the loop going forwards
the best for space 4 would be 6, which uses the item twice
And the space loop also goes from the capacity downwards because you do not want to waste time on the small spaces that cannot hold the item at all.
And the complexity is O of the number of items times the capacity for the time, and O of capacity for the space. The one dimensional version uses much less memory than the two dimensional one from the next question.
So the rule to remember is this. The space loop goes backwards, because each item can be used only once.
The next two questions in this topic show the two dimensional table and how to find the items.