Knapsack problem/Continuous: Difference between revisions

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>