Hi Azrad. An Item is a simple object with a weight and a value. Here is the code:
Code
class Item(object):
def __init__(self, name, value, weight):
self.name = name
self.value = value
self.weight = weight
def getWeight(self):
return self.weight
def getValue(self):
return self.value
def __str__(self):
return self.name
def __repr__(self):
return str((self.name, self.value, self.weight))
An itemlist parameter contains an arbitrary number of Item objects. The knapsack function is supposed to find out the maximum value of items you can put into a sack with a maximum carrying weight of 'capacity'.
Quote (Azrad @ Oct 25 2013 08:55pm)
I assume it must be sorted heaviest to lightest?
Sorting the list is not required, but you can speed up the algorithm by sorting the list once on the first call of the function. I have done this in the improved code (see below).
Also, I have found out the answer to question 2: Once given a list parameter, any sublist is completely defined by its length, since the list is not shuffled throughout the function calls, and each function call (unless it hits the base case) cuts off the first element from the list.
Since 1 and 2 are answered, my new question would be how to speed up the improved algorithm even further. Here's the code:
Code
def knapsack(itemlist, capacity, table = {}, totals = None, presorted = False, VAL = 0, WEIGHT = 1):
""" Given a list of items and a maximum capacity, returns globally optimal solution
to 0/1 knapsack problem as (total value, items to take).
Default parameters:
table: stores subsolutions by mapping (length of sublist, capacity left) tuples
to (total value, items to take) tuples.
totals: list keeping track of total value and weight of items yet to consider.
presorted: specifies whether itemlist is sorted by weight.
VAL, WEIGHT: constants for readability. """
# sort itemlist from lightest to heaviest item (once)
if not presorted:
itemlist = sorted(itemlist, key = lambda item: item.getWeight())
# base cases
consider = itemlist[0]
if not itemlist or capacity == 0 or capacity < consider.getWeight():
return (0, ())
# table lookup
if (len(itemlist), capacity) in table:
return table[(len(itemlist), capacity)]
# init totals (once)
if totals == None:
totalVal, totalWeight = 0, 0
for item in itemlist:
totalVal += item.getValue()
totalWeight += item.getWeight()
totals = [totalVal, totalWeight]
# try to take everything
if capacity >= totals[WEIGHT]:
result = (totals[VAL], tuple(itemlist))
else:
# update totals for itemlist[1:]
totals = totals[:]
totals[VAL] -= consider.getValue()
totals[WEIGHT] -= consider.getWeight()
# explore: take item
capacityLeft = capacity - consider.getWeight()
takeVal, takeList = knapsack(itemlist[1:], capacityLeft, table, totals, True)
takeVal += consider.getValue()
# explore: don't take item
dontVal, dontList = knapsack(itemlist[1:], capacity, table, totals, True)
# choose better result
if takeVal > dontVal:
result = (takeVal, takeList + (consider,))
else:
result = (dontVal, dontList)
# update table and return
table[(len(itemlist), capacity)] = result
return result