Rosetta Code

Knapsack problem/Unbounded: Difference between revisions

← Older editNewer edit →
Content deleted Content added
Line 510:
 
===General Solution===
Requires Python V.2.6+
<python>
<python>from itertools import product, izip
from collections import namedtuple
from pprint import pprint as pp
 
Bounty = namedtuple('Bounty', 'name value weight volume')
items = [ Bounty('panacea', 3000, 0.3, 0.025),▼
Bounty('ichor', 1800, 0.2, 0.015),▼
Bounty('gold', 2500, 2.0, 0.002),▼
]
sack = Bounty('sack', 0, 25.0, 0.25) ▼
 
▲sack = Bounty('sack', 0, 25.0, 0.25)
def totvalue(itemscount, items=items, sack=sack):
 
"""\▼
▲items = [ Bounty('panacea', 3000, 0.3, 0.025),
▲ Bounty('ichor', 1800, 0.2, 0.015),
▲ Bounty('gold', 2500, 2.0, 0.002),]
 
 
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.
Line 529 ⟶ 530:
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) )▼
volumeweight = sum( n * item.volumeweight for n, item in zipizip(itemscountitems_count, items) )
▲ weightvolume = sum( n * item.weightvolume for n, item in zipizip(itemscountitems_count, items) )
if weight ><= sack.weight orand volume ><= sack.volume:
return sum( n * item.value for n, item in zipizip(itemscountitems_count, items) ), -weight, -volume ▼
'''else:▼
return -1, 0, 0
▲ return sum( n*item.value for n, item in zip(itemscount, items) ), -weight, -volume
 
 
def knapsack(items = items, sack = sack):
maxitems =def knapsack():▼
▲ '''
global items, sack
'''
# find max of any one item
max1 = [ min(int(sack.weight // item.weight), int(sack.volume // item.volume)) for item in items]
for item in items ]▼
 
# Try all combinations of bounty items from 0 up to max1
return max( product(*[rangexrange(n + 1) for n in max1]), key = totvalue tot_value)
 
▲maxitems = knapsack()
maxvalue, maxweight, maxvolume = totvalue(maxitems)
maxweight = -maxweight; maxvolume = -maxvolume
 
max_items = knapsack()
print "The maximum value achievable (by exhaustive search) is %g" % maxvalue▼
maxvalue, 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 %.3g, and the volume used is %.3g" % (▼
maxweight, maxvolume )
 
▲print "The maximum value achievable (by exhaustive search) is %g." % maxvalue
# debug print of sorted values
▲item_names = ", ".join(item.name for item in items ])
#max1 = [ min(int(sack.weight/item.weight), int(sack.volume/item.volume))
▲print " The number of %s items to achieve this is: %s, respectively." % (item_names, max_items)
# for item in items ]
▲print " The weight to carry is %.3g, and the volume used is %.3g." % (max_weight, max_volume)
#pp( sorted( (totvalue(num), num) for num in product(*[range(n+1) for n in max1]) )[-20:] )
</python>
 
Sample output
<pre>The maximum value achievable (by exhaustive search) is 54500
The number of panacea, ichor, gold items to achieve this is: (9, 0, 11), respectively
The weight to carry is 24.7, and the volume used is 0.247</pre>
 
Retrieved from "https://rosettacode.org/wiki/Knapsack_problem/Unbounded"