Knapsack problem/Unbounded/Python dynamic programming: Difference between revisions

{{collection|Knapsack problem/Unbounded}}

 

This solution trades off having to search over all possible combinations of items by having to enumerate over all possible sizes of (weight, volume) for each item. The example builds in complexity to the final DP program.

 

A brute-force solution for items with only one 'size' attribute would look like the following and would not scale:

<lang python>from operator import itemgetter as iget

</lang>

 

The dynamic programming version where 'size' has only one dimension would be the following and produces an optimal solution:

<lang python>def knapsack_unbounded_dp(items, C):

return value, size, numbagged, bagged</lang>

 

Our original problem has two dimensions to 'size': weight and volume. We can create a python size object, that knows how to enumerate itself over its given dimensions, as well as perform logical and simple mathematical operations. With the use of the Size object, a correct solution to the given unbounded knapsack problem can be found by the following proceedure:

<lang python>from knapsack_sizer import makesize

print(capacity, dp)</lang>

 

The solution found is printed as:

<pre>Size(wt=250, vol=250) (54500, Size(247, 247), 20, [('gold', 11), ('panacea', 9)])</pre>

I.e. a choice of 20 items: 11 gold and 9 panacea, for a total value of 54500.

 

An ancillary file called knapsack_sizer.py must be made available on your PYTHONPATH with the following contents:

<lang python>from operator import itemgetter as _itemgetter