Anonymous user
Knapsack problem/Unbounded/Python dynamic programming: Difference between revisions
Knapsack problem/Unbounded/Python dynamic programming (view source)
Revision as of 15:02, 22 August 2023
, 9 months ago→Brute force, single size attribute
imported>Katsumi |
|||
| (4 intermediate revisions by 4 users not shown) | |||
Line 1:
{{collection|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.
A brute-force solution for items with only one 'size' attribute would look like the following and would not scale:
<syntaxhighlight lang="python">
from itertools import product
from random import shuffle
Line 45:
return value, size, numbagged, bagged
</syntaxhighlight>
</lang>▼
The dynamic programming version where 'size' has only one dimension would be the following and produces an optimal solution:
<syntaxhighlight lang="python">
# order by max value per item size
items = sorted(items, key=lambda item: item[VALUE]/float(item[SIZE]), reverse=True)
Line 73 ⟶ 74:
bagged = sorted((items[i][NAME], n) for i,n in enumerate(bagged) if n)
return value, size, numbagged, bagged
</syntaxhighlight>
Our original problem has two dimensions to 'size': weight and volume. We can create a python size object, that
<syntaxhighlight lang="python">
Size = makesize('wt vol')
Line 117 ⟶ 120:
dp = knapsack_unboundedmulti_dp(items, capacity)
print(capacity, dp)
</syntaxhighlight>
The solution found is printed as:
<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:
<syntaxhighlight lang="python">
from collections import namedtuple as _namedtuple
from math import sqrt as _sqrt
Line 137 ⟶ 144:
'''
Return Size, an extended namedtuple that represents a container
of N integer
a dimension cannot be less than zero and will instead force all
dimensions to zero.
Line 419 ⟶ 426:
Size = makesize('wt vol')
x,y = Size(*[1,2]), Size(*[3,4])
</syntaxhighlight>
| |||