# Knapsack problem/Unbounded/Python dynamic programming

Knapsack problem/Unbounded/Python dynamic programming is part of Knapsack problem/Unbounded. You may find other members of Knapsack problem/Unbounded at Category:Knapsack problem/Unbounded.

## Dynamic Programming Solution

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.

### 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: <lang python>from operator import itemgetter as iget from itertools import product from random import shuffle

NAME, SIZE, VALUE = range(3) items = (

```   # NAME, SIZE, VALUE
('A', 3, 2),
('B', 5, 4),
('C', 7, 6),
('D', 9, 8) )
```

capacity = 8

def knapsack_unbounded_enumeration(items, C):

```   # find max of any one item
max1 = [ int(C/item[SIZE]) for item in items ]
itemsizes  = [ item[SIZE]  for item in items ]
itemvalues = [ item[VALUE] for item in items ]
```
```   #def totvalue(itemscount, =itemsizes, itemvalues=itemvalues, C=C):
def totvalue(itemscount):
nonlocal itemsizes, itemvalues, C

totsize = sum( n*size for n, size in zip(itemscount, itemsizes) )
totval  = sum( n*val  for n, val  in zip(itemscount, itemvalues) )

return (totval, -totsize) if totsize <= C else (-1, 0)
```
```   # Try all combinations of bounty items from 0 up to max1
bagged = max( product(*[range(n+1) for n in max1]), key = totvalue )
numbagged = sum(bagged)
value, size = totvalue(bagged)
size = -size
# convert to (iten, count) pairs) in name order
bagged = sorted((items[i][NAME], n) for i,n in enumerate(bagged) if n)
```
```   return value, size, numbagged, bagged
```

</lang>

### DP, single size dimension

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):

```   # order by max value per item size
items = sorted(items, key=lambda item: item[VALUE]/float(item[SIZE]), reverse=True)

# Sack keeps track of max value so far as well as the count of each item in the sack
sack = [(0, [0 for i in items]) for i in range(0, C+1)]   # value, [item counts]

for i,item in enumerate(items):
name, size, value = item
for c in range(size, C+1):
sackwithout = sack[c-size]  # previous max sack to try adding this item to
trial = sackwithout + value
used = sackwithout[i]
if sack[c] < trial:
# old max sack with this added item is better
sack[c] = (trial, sackwithout[:])
sack[c][i] +=1   # use one more
```
```   value, bagged = sack[C]
numbagged = sum(bagged)
size = sum(items[i]*n for i,n in enumerate(bagged))
# convert to (iten, count) pairs) in name order
bagged = sorted((items[i][NAME], n) for i,n in enumerate(bagged) if n)
```
```   return value, size, numbagged, bagged</lang>
```

### 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: <lang python>from knapsack_sizer import makesize

Size = makesize('wt vol')

items = [

```   # NAME, (WT, VOL), VALUE
('panacea', Size(3, 25), 3000),
('ichor', Size(2, 15), 1800),
('gold', Size(20, 2), 2500) ]
```

capacity = Size(250, 250)

def knapsack_unboundedmulti_dp(items, C):

```   # order by max value per item size
items = sorted(items, key=lambda item: item[VALUE]/abs(item[SIZE]), reverse=True)

# Sack keeps track of max value so far as well as the count of each item in the sack
zero, one = tuple(zip(*((0,1) for i in C)))
sack = dict( (i, (0, [0 for i in items]))   # size -> (value, [item counts])
for i in C.range(C+one) )

for i,item in enumerate(items):
name, size, value = item
for c in C.range(size, C+one):
sackwithout = sack[c-size]  # previous max sack to try adding this item to
trial = sackwithout + value
used = sackwithout[i]
if sack[c] < trial:
# old max sack with this added item is better
sack[c] = (trial, sackwithout[:])
sack[c][i] +=1   # use one more
```
```   value, bagged = sack[C]
numbagged = sum(bagged)
size = sum((items[i]*n for i,n in enumerate(bagged)), zero)
# convert to (iten, count) pairs) in name order
bagged = sorted((items[i][NAME], n) for i,n in enumerate(bagged) if n)
```
```   return value, size, numbagged, bagged
```

dp = knapsack_unboundedmulti_dp(items, capacity) print(capacity, dp)</lang>

### Sample output

The solution found is printed as:

`Size(wt=250, vol=250) (54500, Size(247, 247), 20, [('gold', 11), ('panacea', 9)])`

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: <lang python>from operator import itemgetter as _itemgetter from collections import namedtuple as _namedtuple from math import sqrt as _sqrt from itertools import product as _product from numbers import Number as _Number

_tuple = tuple

def makesize(dimensionnames, typename='Size'):

```
Return Size, an extended namedtuple that represents a container
of N integer independent dimensions, e.g. weight and volume
a dimension cannot be less than zero and will instead force all
dimensions to zero.
```
```   Some tests

>>> Size = makesize('wt vol')
>>> Size(wt=1, vol=2)
Size(1, 2)
>>> Size(1, vol=2)
Size(1, 2)
>>> Size(vol=2, wt=1)
Size(1, 2)

>>> x,y = Size(*[1,2]), Size(*[3,4])
>>> x
Size(1, 2)
>>> y
Size(3, 4)
>>> str(x)
'Size(wt=1, vol=2)'
>>> str(y)
'Size(wt=3, vol=4)'
>>> Size(*[1,-2])
Size(0, 0)
>>> Size(*[-1,2])
Size(0, 0)
>>> x
Size(1, 2)
>>> x.wt
1
>>> x.vol
2
>>> x
1
>>> x
2
>>> x+[1,1]
Size(2, 3)
>>> (1,1)+x
Size(2, 3)
>>> [1,1]+x
Size(2, 3)
>>> x+(1,1)
Size(2, 3)
>>> x-[1,1]
Size(0, 1)
>>> [2,4]-x
Size(1, 2)
>>> (2,4)-x
Size(1, 2)
```
```   >>> # Comparisons
```
```   >>> Size = makesize('wt vol')
>>> for s in ((i,j) for i in (0,1,2) for j in (1,2,3)):
...         for op in '== != < <= >= >'.split():
...                 eqn = '%s %2s %r' % (str(s), op, Size(*[1,2]))
...                 print("%25r" % eqn, '=', eval(eqn))
...
...
'(0, 1) == Size(1, 2)' = False
'(0, 1) != Size(1, 2)' = True
'(0, 1)  < Size(1, 2)' = True
'(0, 1) <= Size(1, 2)' = True
'(0, 1) >= Size(1, 2)' = False
'(0, 1)  > Size(1, 2)' = False
'(0, 2) == Size(1, 2)' = False
'(0, 2) != Size(1, 2)' = True
'(0, 2)  < Size(1, 2)' = True
'(0, 2) <= Size(1, 2)' = True
'(0, 2) >= Size(1, 2)' = False
'(0, 2)  > Size(1, 2)' = False
'(0, 3) == Size(1, 2)' = False
'(0, 3) != Size(1, 2)' = True
'(0, 3)  < Size(1, 2)' = False
'(0, 3) <= Size(1, 2)' = False
'(0, 3) >= Size(1, 2)' = False
'(0, 3)  > Size(1, 2)' = False
'(1, 1) == Size(1, 2)' = False
'(1, 1) != Size(1, 2)' = True
'(1, 1)  < Size(1, 2)' = True
'(1, 1) <= Size(1, 2)' = True
'(1, 1) >= Size(1, 2)' = False
'(1, 1)  > Size(1, 2)' = False
'(1, 2) == Size(1, 2)' = True
'(1, 2) != Size(1, 2)' = False
'(1, 2)  < Size(1, 2)' = False
'(1, 2) <= Size(1, 2)' = True
'(1, 2) >= Size(1, 2)' = True
'(1, 2)  > Size(1, 2)' = False
'(1, 3) == Size(1, 2)' = False
'(1, 3) != Size(1, 2)' = True
'(1, 3)  < Size(1, 2)' = False
'(1, 3) <= Size(1, 2)' = False
'(1, 3) >= Size(1, 2)' = True
'(1, 3)  > Size(1, 2)' = True
'(2, 1) == Size(1, 2)' = False
'(2, 1) != Size(1, 2)' = True
'(2, 1)  < Size(1, 2)' = False
'(2, 1) <= Size(1, 2)' = False
'(2, 1) >= Size(1, 2)' = False
'(2, 1)  > Size(1, 2)' = False
'(2, 2) == Size(1, 2)' = False
'(2, 2) != Size(1, 2)' = True
'(2, 2)  < Size(1, 2)' = False
'(2, 2) <= Size(1, 2)' = False
'(2, 2) >= Size(1, 2)' = True
'(2, 2)  > Size(1, 2)' = True
'(2, 3) == Size(1, 2)' = False
'(2, 3) != Size(1, 2)' = True
'(2, 3)  < Size(1, 2)' = False
'(2, 3) <= Size(1, 2)' = False
'(2, 3) >= Size(1, 2)' = True
'(2, 3)  > Size(1, 2)' = True
```
```   >>> # Same comparison answers with lists on LHS
>>> cmplst = [eval('%s %2s %r' % (str(s), op, Size(*[1,2])))  for s in ([i,j] for i in (0,1,2) for j in (1,2,3))  for op in '== != < <= >= >'.split() ]
>>> # Same comparison answers with tuples on LHS
>>> cmptpl = [eval('%s %2s %r' % (str(s), op, Size(*[1,2])))  for s in ((i,j) for i in (0,1,2) for j in (1,2,3))  for op in '== != < <= >= >'.split() ]
>>> assert cmplst == cmptpl
>>>
```
```

tmp = _namedtuple(typename, dimensionnames)
_fields = tmp._fields
class Size(tmp):
__doc__ = tmp.__doc__ + '\n\n' + makesize.__doc__
```
```       __slots__ = ()
```
```       def __new__(_cls, *args0, **kwargs):
nonlocal tmp
a = []
lenargs0 = len(args0)
if lenargs0> len(tmp._fields):
raise ValueError('Got unexpected extra %d fields' % (lenargs0 - len(tmp._fields),))
for i,name in enumerate(tmp._fields):
if i<lenargs0:
a.append(args0[i])
if name in kwargs:
raise ValueError('Argument given twice: %r' % name)
elif name in kwargs:
a.append(kwargs.pop(name))
else:
raise ValueError('Missing field name: %r' % name)
if kwargs:
raise ValueError('Got unexpected field names: %r' % kwargs.keys())
args = a
if any(arg<0 for arg in args): args = tuple(0 for arg in args)
return _tuple.__new__(_cls, args)
```
```       @classmethod
def _make(cls, iterable, new=tuple.__new__, len=len):
'Make a new Size object from a sequence or iterable'
args = tuple(iterable)
if any(arg<0 for arg in args): args = tuple(0 for arg in args)
result = new(cls, args)
if len(result) != len(cls._fields):
raise TypeError('Expected %d arguments, got %d' % (len(cls._fields),
len(result)))
return result
```
```       def range(_self, start, stop=None):

range([start,] stop) -> itertools.product object
Returns an iterator that generates the sizes in the range on demand as tuples.

if stop is None:
stop = start
start = tuple(0 for i in _self)
if len(_self) != len(start):
raise TypeError('Expected %d elements in start, got %d' % (len(_self), len(start)))
if len(_self) != len(stop):
raise TypeError('Expected %d elements in stop, got %d' % (len(_self), len(stop)))
return _product(*(range(mn,mx) for mn,mx in zip(start, stop)))
```
```       __hash__ = _tuple.__hash__
```
```       def __mul__(_self, y):
'Return a new Size object where corresponding elements are multiplied by y'
if isinstance(y, _Number):
return _self._make( x*y for x in _self)
elif len(_self) == len(y):
return _self._make( ex*ey for ex,ey in zip(_self, y))
else:
raise NotImplementedError('Expected a Number or a %d element tuple/list, got %r' % (
len(_self), y))
def __truediv__(_self, y):
'Return a new Size object where corresponding elements are divided by y'
if isinstance(y, _Number):
return _self._make( x/y for x in _self)
elif len(_self) == len(y):
return _self._make( ex/ey for ex,ey in zip(_self, y))
else:
raise NotImplementedError('Expected a Number or a %d element tuple/list, got %r' % (
len(_self), y))
```
```       def __repr__(self):
return 'Size(' + ', '.join('%r' % i for i in self) + ')'
def __str__(self):
return 'Size(' + ', '.join('%s=%r' % i for i in zip(self._fields, self)) + ')'
```
```       def __abs__(_self):
'Return the sqrt of the sum of the squares of all elements'
return _sqrt(sum(e*e for e in _self))
```
```       def __add__(_self, y):
'Return a new Size object where corresponding elements are added'
if len(_self) != len(y):
raise TypeError('Expected %d arguments, got %d' % (len(_self), len(y)))
return _self._make( x+y for x,y in zip(_self, y))
'Return a new Size object where corresponding elements are added'
if len(_self) != len(y):
raise TypeError('Expected %d arguments, got %d' % (len(_self), len(y)))
return _self._make( y+x for x,y in zip(_self, y))
```
```       def __sub__(_self, y):
'Return a new Size object where corresponding elements are subtracted'
if len(_self) != len(y):
raise TypeError('Expected %d arguments, got %d' % (len(_self), len(y)))
return _self._make( x-y for x,y in zip(_self, y))
def __rsub__(_self, y):
'Return a new Size object where corresponding elements are subtracted'
if len(_self) != len(y):
raise TypeError('Expected %d arguments, got %d' % (len(_self), len(y)))
return _self._make( y-x for x,y in zip(_self, y))
```
```       def __eq__(_self, y):
'Return true iff all fields of self == y'
if len(_self) != len(y):
raise TypeError('Expected %d arguments, got %d' % (len(_self), len(y)))
return all(x == y for x,y in zip(_self, y))
def __ne__(_self, y):
'Return true iff any fields of self != y'
if len(_self) != len(y):
raise TypeError('Expected %d arguments, got %d' % (len(_self), len(y)))
return any(x != y for x,y in zip(_self, y))
```
```       def __gt__(_self, y):
'Return true iff all fields of self >= y and at least one field is > its field in y'
if len(_self) != len(y):
raise TypeError('Expected %d arguments, got %d' % (len(_self), len(y)))
more = False
for x,y in zip(_self, y):
if x > y: more = True
if x < y: break
else:
return more
return False
def __ge__(_self, y):
'Return true iff all fields of self >= y'
if len(_self) != len(y):
raise TypeError('Expected %d arguments, got %d' % (len(_self), len(y)))
return all(x >= y for x,y in zip(_self, y))
def __lt__(_self, y):
'Return true iff all fields of self <= y and at least one field is < its field in y'
if len(_self) != len(y):
raise TypeError('Expected %d arguments, got %d' % (len(_self), len(y)))
more = False
for x,y in zip(_self, y):
if x < y: more = True
if x > y: break
else:
return more
return False
def __le__(_self, y):
'Return true iff all fields of self >= y'
if len(_self) != len(y):
raise TypeError('Expected %d arguments, got %d' % (len(_self), len(y)))
return all(x <= y for x,y in zip(_self, y))
```
```   return Size
```

if __name__ == '__main__':

```   import doctest
doctest.testmod(verbose=not True)
Size = makesize('wt vol')
x,y = Size(*[1,2]), Size(*[3,4])
```

</lang>