BinaryKnapsack.py

class Item:
    
    def __init__(self, id, weight, profit):
        self.id = id
        self.weight = weight 
        self.profit = profit


def binaryKnapsack(knapsackMaxWeight, items):
    """
    Creates a multi-dimensional list that contains maximum profits associated with inserting items
    up to a given knapsack weight. The results are limited by the number of items and the maximum
    possible knapsack weight. Returns the ids of the items that optimally fill up the knapsack.
    
    Assume 'n' represents the number of items and 'm' represents the knapsack's maximum weight:
        The run-time is O(n*m)
        The space requirement is O(n*m).    
    """
    
    memoizedKnapsack = [[0]*(knapsackMaxWeight+1) for i in range(len(items)+1)]
    
    for itemIndex in range(len(items)+1):
        for knapsackWeight in range(1, knapsackMaxWeight+1):
            if items[itemIndex-1].weight > knapsackWeight:
                memoizedKnapsack[itemIndex][knapsackWeight] = memoizedKnapsack[itemIndex-1][knapsackWeight]
            else:
                if itemIndex > 0 and knapsackWeight >= items[itemIndex-1].weight:
                    inclusiveWeight = memoizedKnapsack[itemIndex-1][knapsackWeight-items[itemIndex-1].weight] + items[itemIndex-1].profit
                    if memoizedKnapsack[itemIndex-1][knapsackWeight] > inclusiveWeight:
                        memoizedKnapsack[itemIndex][knapsackWeight] = memoizedKnapsack[itemIndex-1][knapsackWeight]
                    else:
                        memoizedKnapsack[itemIndex][knapsackWeight] = inclusiveWeight
    
    # Retrieve ids of items that optimally fill up the knapsack
    itemIds = []
    itemIndex = len(memoizedKnapsack)-1                    
    knapsackWeight = len(memoizedKnapsack[itemIndex])-1
    while itemIndex > 0 and knapsackWeight > 0:
        if memoizedKnapsack[itemIndex][knapsackWeight] != memoizedKnapsack[itemIndex-1][knapsackWeight]:
            itemIds.append(items[itemIndex-1].id)
            knapsackWeight -= items[itemIndex-1].weight        
        itemIndex -= 1
    itemIds.sort()
    return itemIds
        
                    
if __name__ == "__main__":
    items = [Item("Hatchet", 4, 20), Item("Henry David Thoreau's 'Walden'", 1, 15), Item("Laptop", 5, 6)]
    
    print binaryKnapsack(5, items) 
    # Expected output -- "['Hatchet', "Henry David Thoreau's 'Walden'"]"

class Item:
    def __init__(self, name, weight, profit):
        self.name = name 
        self.weight = weight 
        self.profit = profit

def knapsack(max, items):
    knap = [[0]*(max+1) for i in range(len(items)+1)]
    # iterate through items
    for idx in range(1,len(items)+1):
        cur = items[idx-1] # corrects for zero-base
        # iterate through knapsack weights
        for knapW in range(1, max+1):
            if cur.weight > knapW:
                knap[idx][knapW] = knap[idx-1][knapW]
            else:
                inc = knap[idx-1][knapW - cur.weight] + cur.profit
                if knap[idx-1][knapW] > inc:
                    knap[idx][knapW] = knap[idx-1][knapW]
                else:
                    knap[idx][knapW] = inc
    stuff = []
    while idx > 0 and knapW > 0:
        if knap[idx][knapW] != knap[idx-1][knapW]:    # item was added
            stuff.append(items[idx-1].name)
            knapW -= items[idx-1].weight
        idx-=1
    stuff.sort()
    return stuff

items = [
    Item("Hatchet", 4, 20),
    Item("Henry David Thoreau's 'Walden'", 1, 15),
    Item("Laptop", 5, 6)
]
print knapsack(5, items)

I made this version, which is more readable to me, but maybe not to everyone else