0/1 Knapsack Problem - Recursive

gistfile1.py

############################################################
############################################################
###
### 0/1 knapsack
###
############################################################
############################################################

# from earlier lecture...
class Item(object):
    def __init__(self, n, v, w):
        self.name = n
        self.value = float(v)
        self.weight = float(w)
    def getName(self):
        return self.name
    def getValue(self):
        return self.value
    def getWeight(self):
        return self.weight
    def __repr__(self):
        return 'Item(' + self.name + ', ' + str(self.value) + ', '\
                     + str(self.weight) + ')'

# choose most valuable selection of items that will fit
# returns (total_value,item_sequence)
def chooseBest(items,maxWeight):
    if len(items) == 0 or maxWeight <= 0:
        return (0,())
    first = items[0]
    w = first.getWeight()
    rest = items[1:]

    # alternative 1: don't include first item in knapsack
    v1,t1 = chooseBest(rest,maxWeight)

    # alternative 2: include first item in knapsack
    # remember to leave room for first item in knapsack
    v2,t2 = chooseBest(rest,maxWeight - w)
    v2 += first.getValue()  # now include first item
    t2 += (first,)

    # choose most valuable alternative (choice 2 is
    # possible only if first item fits in knapsack)
    return (v2,t2) if w <= maxWeight and v2 >= v1 else (v1,t1)
    
 
fewItems = tuple(Item(n,v,w) for n,v,w in (('clock', 175, 10),
                                            ('painting', 90, 9),
                                            ('radio', 20, 4),
                                            ('vase', 50, 2),
                                            ('book', 10, 1),
                                            ('computer', 200, 20)))

# build a tuple of n items of various weights and values
import random
def buildRandomItems(n):
    return tuple(Item(str(i),
                       10*random.randint(1,10),
                       random.randint(1,5))
                  for i in xrange(n))

# chooseBest(manyItems,20) completes only if chooseBest is memoized
manyItems = buildRandomItems(50)

def testChooseBest(items,maxWeight):
    value, result = chooseBest(items,maxWeight)
    print '*** total value of items in knapsack =',value
    for item in result: print '    ',item