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 |
imported>Katsumi |
||
Line 45:
return value, size, numbagged, bagged
</syntaxhighlight>
</lang>▼
===DP, single size dimension===
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>
===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:
<syntaxhighlight lang="python">
Size = makesize('wt vol')
Line 117 ⟶ 120:
dp = knapsack_unboundedmulti_dp(items, capacity)
print(capacity, dp)
</syntaxhighlight>
===Sample output===
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.
===Ancillary module===
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
|