67 lines
2.0 KiB
Python
67 lines
2.0 KiB
Python
from itertools import groupby
|
|
|
|
try:
|
|
xrange
|
|
except:
|
|
xrange = range
|
|
|
|
maxwt = 400
|
|
|
|
groupeditems = (
|
|
("map", 9, 150, 1),
|
|
("compass", 13, 35, 1),
|
|
("water", 153, 200, 3),
|
|
("sandwich", 50, 60, 2),
|
|
("glucose", 15, 60, 2),
|
|
("tin", 68, 45, 3),
|
|
("banana", 27, 60, 3),
|
|
("apple", 39, 40, 3),
|
|
("cheese", 23, 30, 1),
|
|
("beer", 52, 10, 3),
|
|
("suntan cream", 11, 70, 1),
|
|
("camera", 32, 30, 1),
|
|
("t-shirt", 24, 15, 2),
|
|
("trousers", 48, 10, 2),
|
|
("umbrella", 73, 40, 1),
|
|
("waterproof trousers", 42, 70, 1),
|
|
("waterproof overclothes", 43, 75, 1),
|
|
("note-case", 22, 80, 1),
|
|
("sunglasses", 7, 20, 1),
|
|
("towel", 18, 12, 2),
|
|
("socks", 4, 50, 1),
|
|
("book", 30, 10, 2),
|
|
)
|
|
items = sum( ([(item, wt, val)]*n for item, wt, val,n in groupeditems), [])
|
|
|
|
def knapsack01_dp(items, limit):
|
|
table = [[0 for w in range(limit + 1)] for j in xrange(len(items) + 1)]
|
|
|
|
for j in xrange(1, len(items) + 1):
|
|
item, wt, val = items[j-1]
|
|
for w in xrange(1, limit + 1):
|
|
if wt > w:
|
|
table[j][w] = table[j-1][w]
|
|
else:
|
|
table[j][w] = max(table[j-1][w],
|
|
table[j-1][w-wt] + val)
|
|
|
|
result = []
|
|
w = limit
|
|
for j in range(len(items), 0, -1):
|
|
was_added = table[j][w] != table[j-1][w]
|
|
|
|
if was_added:
|
|
item, wt, val = items[j-1]
|
|
result.append(items[j-1])
|
|
w -= wt
|
|
|
|
return result
|
|
|
|
|
|
bagged = knapsack01_dp(items, maxwt)
|
|
print("Bagged the following %i items\n " % len(bagged) +
|
|
'\n '.join('%i off: %s' % (len(list(grp)), item[0])
|
|
for item,grp in groupby(sorted(bagged))))
|
|
print("for a total value of %i and a total weight of %i" % (
|
|
sum(item[2] for item in bagged), sum(item[1] for item in bagged)))
|