Anonymous user
Knapsack Problem/Python: Difference between revisions
→More General Dynamic Programming solution: One too many?
(moved from Knapsack Problem) |
(→More General Dynamic Programming solution: One too many?) |
||
Line 91:
The weight to carry is 24.7, and the volume used is 0.247</pre>
===
A dynamic programming approach using a 2-dimensional table (One dimension for weight and one for volume). Because this approach requires that all weights and volumes be integer, I multiplied the weights and volumes by enough to make them integer. This algorithm takes O(w*v) space and O(w*v*n) time, where w = weight of sack, v = volume of sack, n = number of types of items. To solve this specific problem it's much slower than the brute force solution.
Line 185:
The number of panacea,ichor,gold items to achieve this is: [9, 0, 11], respectively
The weight to carry is 247, and the volume used is 247</pre>
===More General Dynamic Programming solution===
See [[Knapsack problem/Unbounded/Python dynamic programming]]
| |||