Knapsack problem/Unbounded: Difference between revisions

Content added Content deleted
Line 510: Line 510:


===General Solution===
===General Solution===
Requires Python V.2.6+
<python>
from itertools import product
<python>from itertools import product, izip
from collections import namedtuple
from collections import namedtuple
from pprint import pprint as pp


Bounty = namedtuple('Bounty', 'name value weight volume')
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.
Given the count of each item in the sack return -1 if they can't be carried or their total value.
Line 529: Line 530:
values will minimise the weight if values tie, and minimise the volume if values and weights tie).
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) )
volume = sum( n*item.volume for n, item in zip(itemscount, items) )
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))
if weight > sack.weight or volume > sack.volume:
if weight <= sack.weight and volume <= sack.volume:
⚫
return sum(n * item.value for n, item in izip(items_count, items)), -weight, -volume
⚫
else:
return -1, 0, 0
return -1, 0, 0
⚫
return sum( n*item.value for n, item in zip(itemscount, items) ), -weight, -volume



def knapsack(items = items, sack = sack):
⚫
def knapsack():
⚫
'''
global items, sack
'''
# find max of any one item
# find max of any one item
max1 = [ min(int(sack.weight/item.weight), int(sack.volume/item.volume))
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
# Try all combinations of bounty items from 0 up to max1
return max( product(*[range(n+1) for n in max1]), key = totvalue )
return max(product(*[xrange(n + 1) for n in max1]), key=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>
</python>


Sample output
Sample output
<pre>The maximum value achievable (by exhaustive search) is 54500
<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 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>
The weight to carry is 24.7, and the volume used is 0.247</pre>


Retrieved from "https://rosettacode.org/wiki/Knapsack_problem/Unbounded"