Anonymous user
Knapsack problem/Unbounded: Difference between revisions
→General Dynamic Programming solution
Line 566:
===General Dynamic Programming solution===
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(
<python>
<python>from collections import namedtuple▼
from itertools import product, izip
Bounty = namedtuple('Bounty', 'name value weight volume')
# "namedtuple" is only available in Python 2.6+; for earlier versions use this instead:
# class Bounty:
Line 579 ⟶ 582:
# self.volume = volume
Bounty('ichor', 1800, 2, 15),▼
Bounty('gold', 2500, 20, 2),▼
items = [Bounty('panacea', 3000, 3, 25),
"""\▼
def tot_value(items_count):
Given the count of each item in the sack return -1 if they can't be carried or their total value.
(also return the negative of the weight and the volume so taking the max of a series of return
values will minimise the weight if values tie, and minimise the volume if values and weights tie).
"""
global items, sack
weight = sum( n*item.weight for n, item in zip(itemscount, items) )▼
if weight
return sum(
▲ else:
return -1, 0, 0
▲ return sum( n*item.value for n, item in zip(itemscount, items) ), -weight, -volume
def knapsack_dp(
"""
Solves the Knapsack problem, with two sets of weights,
using a dynamic programming approach
"""
global items, sack
# (weight+1) x (volume+1) table
Line 608 ⟶ 616:
# with a sack of weight w and volume v.
# They all start out as 0 (empty sack)
table = [
for w in
for v in
# Consider the optimal solution, and consider the "last item" added
# to the sack. Removing this item must produce an optimal solution
Line 619 ⟶ 627:
# Only consider items that would fit:
if w >= item.weight and v >= item.volume:
table[w][v] =
# Backtrack through matrix to re-construct optimum:
result = [0] * len(items)
w = sack.weight
while table[w][v]:
# Find the last item that was added:
i = [table[w-item.weight][v-item.volume] + item.value for item in items].index(table[w][v])
# Record it in the result, and remove it:
result[i] += 1
Line 638 ⟶ 646:
return result
maxitems = knapsack_dp()▼
print "The maximum value achievable (by dynamic programming) is %g" % maxvalue▼
max_value, max_weight, max_volume = tot_value(max_items)
print " The number of %s items to achieve this is: %s, respectively" % (▼
max_weight = -max_weight
','.join(item.name for item in items), maxitems )▼
max_volume = -max_volume
print " The weight to carry is %d, and the volume used is %d" % (▼
▲print "The maximum value achievable (by
▲print " The number of %s items to achieve this is: %s, respectively." % (item_names, max_items)
</python>
Sample output
| |||