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

===Brute force, single size attribute===

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

from itertools import product

from random import shuffle

 

return value, size, numbagged, bagged

 

===DP, single size dimension===

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

# order by max value per item size

items = sorted(items, key=lambda item: item[VALUE]/float(item[SIZE]), reverse=True)

bagged = sorted((items[i][NAME], n) for i,n in enumerate(bagged) if n)

 

 

===DP, multiple size dimensions===

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:

 

Size = makesize('wt vol')

 

dp = knapsack_unboundedmulti_dp(items, capacity)

 

===Sample output===

The solution found is printed as:

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

 

===Ancillary module===

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

from collections import namedtuple as _namedtuple

from math import sqrt as _sqrt

Size = makesize('wt vol')

x,y = Size(*[1,2]), Size(*[3,4])