Anonymous user
Knapsack problem/Continuous: Difference between revisions
→{{header|Python}}: Greedy is optimal solution?
(→{{header|Python}}: Greedy is optimal solution?) |
|||
Line 265:
=={{header|Python}}==
I think this greedy algorithm of taking the largest amounts of items ordered by their value per unit weight is maximal:
<lang python>items = [ # NAME, WEIGHT, VALUE (for this weight)
('beef', 3.8, 36.0),
('pork', 5.4, 43.0),
('ham', 3.6, 90.0),
('greaves', 2.4, 45.0),
('flitch', 4.0, 30.0),
('brawn', 2.5, 56.0),
('welt', 3.7, 67.0),
('salami', 3.0, 95.0),
('sausage', 5.9, 98.0)]
maxwt = 15.0
sorteditems = sorted( ((value/amount, amount, name)
for name, amount, value in items),
reverse = True)
wt = val = 0
bagged = []
for unitvalue, amount, name in sorteditems:
portion = min(maxwt - wt, amount)
wt += portion
addval = portion * unitvalue
val += addval
bagged += [(name, portion, addval)]
if wt >= maxwt:
break
print(" ITEM PORTION VALUE")
print('\n'.join("%10s %6.2f %6.2f" % item for item in bagged))
print("\nTOTAL WEIGHT: %5.2f\nTOTAL VALUE: %5.2f" % (wt, val))</lang>
'''Sample Output'''
<pre> ITEM PORTION VALUE
salami 3.00 95.00
ham 3.60 90.00
brawn 2.50 56.00
greaves 2.40 45.00
welt 3.50 63.38
TOTAL WEIGHT: 15.00
TOTAL VALUE: 349.38</pre>
| |||