Anonymous user
Knapsack problem/Unbounded: Difference between revisions
→General Dynamic Programming solution
Line 568:
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.
<python>from itertools import product, izip▼
▲from itertools import product, izip
from collections import namedtuple
Line 589 ⟶ 588:
def tot_value(items_count, items, sack):
"""
Given the count of each item in the sack return -1 if they can't be carried or their total value.
Line 596 ⟶ 595:
values will minimise the weight if values tie, and minimise the volume if values and weights tie).
"""
weight = sum(n * item.weight for n, item in izip(items_count, items))
volume = sum(n * item.volume for n, item in izip(items_count, items))
Line 605 ⟶ 603:
def knapsack_dp(items, sack):
"""
Solves the Knapsack problem, with two sets of weights,
using a dynamic programming approach
"""
# (weight+1) x (volume+1) table
# table[w][v] is the maximum value that can be achieved
Line 637 ⟶ 633:
while table[w][v]:
# Find the last item that was added:
i = aux.index(table[w][v])
# Record it in the result, and remove it:
Line 647 ⟶ 644:
max_items = knapsack_dp(items, sack)
max_value, max_weight, max_volume =
max_weight = -max_weight
max_volume = -max_volume
Line 655 ⟶ 652:
item_names = ", ".join(item.name for item in items)
print " The number of %s items to achieve this is: %s, respectively." % (item_names, max_items)
print " The weight to carry is %.3g, and the volume used is %.3g." % (max_weight, max_volume)</python>
Sample output
| |||