The Knapsack Problem, in Python

explained.txt

The numbers in the table indicate the maximum value of the knapsack

The columns of the table indicate the maximum weight.

The rows of the table indicate which items you are allowed to place in the knapsack.

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] === no items
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] === red only
[0, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3] === red and gray
[0, 2, 3, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5] === red, gray, and blue
[0, 2, 3, 4, 10, 12, 13, 14, 15, 15, 15, 15, 15, 15, 15, 15] === red, gray, blue, and yellow
[0, 2, 3, 4, 10, 12, 13, 14, 15, 15, 15, 15, 15, 15, 15, 15] === red, gray, blue, yellow, and green

output.txt

[steve@rosie knapsack]$ python rosettaCodePython.py 
red
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]


gray
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]


blue
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
[0, 2, 3, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]


yellow
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
[0, 2, 3, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
[0, 2, 3, 4, 10, 12, 13, 14, 15, 15, 15, 15, 15, 15, 15, 15]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]


green
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
[0, 2, 3, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
[0, 2, 3, 4, 10, 12, 13, 14, 15, 15, 15, 15, 15, 15, 15, 15]
[0, 2, 3, 4, 10, 12, 13, 14, 15, 15, 15, 15, 15, 15, 15, 15]


Item counter: 5   Weight Limit: 15
Item counter: 4   Weight Limit: 15
[('yellow', 4, 10)]
Item counter: 3   Weight Limit: 11
[('yellow', 4, 10), ('blue', 2, 2)]
Item counter: 2   Weight Limit: 9
[('yellow', 4, 10), ('blue', 2, 2), ('gray', 1, 2)]
Item counter: 1   Weight Limit: 8
[('yellow', 4, 10), ('blue', 2, 2), ('gray', 1, 2), ('red', 1, 1)]
Bagged the following items
  blue
  gray
  red
  yellow
for a total value of 15 and a total weight of 8

rosettaCodePython.py

#!/usr/bin/env python

#import 

def main():


    try:
        xrange
    except:
        xrange = range
    
    def totalvalue(comb):
        ' Totalise a particular combination of items'
        totwt = totval = 0
        for item, wt, val in comb:
            totwt  += wt
            totval += val
        return (totval, -totwt) if totwt <= 400 else (0, 0)
    
    itemsLong = (
        ("map", 9, 150), ("compass", 13, 35), ("water", 153, 200), ("sandwich", 50, 160),
        ("glucose", 15, 60), ("tin", 68, 45), ("banana", 27, 60), ("apple", 39, 40),
        ("cheese", 23, 30), ("beer", 52, 10), ("suntan cream", 11, 70), ("camera", 32, 30),
        ("t-shirt", 24, 15), ("trousers", 48, 10), ("umbrella", 73, 40),
        ("waterproof trousers", 42, 70), ("waterproof overclothes", 43, 75),
        ("note-case", 22, 80), ("sunglasses", 7, 20), ("towel", 18, 12),
        ("socks", 4, 50), ("book", 30, 10),
        )
    
    items = (
        ("red",1,1),("gray",1,2),("blue",2,2),("yellow",4,10),("green",12,4)
        )
    
    def printTable(table):
        for eachRow in table:
            print(eachRow)
        print('\n')
    
    def knapsack01_dp(items, limit):
        
        # create a table for recordkeeping
        # each row of the table indicates a new item becoming available
        # each column of the table indicates a trial weight limit
        
        table = [[0 for w in range(limit + 1)] for itemCounter in xrange(len(items) + 1)]
        
        for itemCounter in xrange(1, len(items) + 1):
            itemName, itemWeight, itemValue = items[itemCounter-1]
            
            for weightCounter in xrange(1, limit + 1):
                if itemWeight > weightCounter:
                    # we can't fit the item in the sack, leave it out
                    # value of the sack = value of the sack without the item
                    table[itemCounter][weightCounter] = table[itemCounter-1][weightCounter]
                else:
                    # we can fit the item in the sack, now we have to decide if
                    # it's worth bringing along.
                    
                    # bringing the item along means that the weight of the sack
                    # will be the previous weight of the sack plus the weight of
                    # the new item
                    # to find the value of the sack with the item, first find 
                    # the value of the sack without the item:
                    # (weightcounter-itemweight)
                    # then add the value of the item you're adding
                    value_if_we_bring_it_along = table[itemCounter-1][weightCounter-itemWeight] + itemValue
                    
                    # The value of the sack if we don't bring the item is whatever
                    # the value of the sack was last time
                    value_if_we_do_not_bring_it = table[itemCounter-1][weightCounter]
                    
                    if value_if_we_bring_it_along > value_if_we_do_not_bring_it:
                        table[itemCounter][weightCounter] = value_if_we_bring_it_along
                    else:
                        table[itemCounter][weightCounter] = value_if_we_do_not_bring_it
            
            print(itemName)
            printTable(table)
        
        result = []
        weightLimit = limit
        for itemCounter in range(len(items), 0, -1):
            print("Item counter: %s   Weight Limit: %s" % (itemCounter,weightLimit) )
            was_added = table[itemCounter][weightLimit] != table[itemCounter-1][weightLimit]
    
            if was_added:
                itemName, itemWeight, itemValue = items[itemCounter-1]
                result.append(items[itemCounter-1])
                weightLimit -= itemWeight
                print(result)
        
        return result
    
    #knapsack01_dp([0,1,2],6)
    bagged = knapsack01_dp(items, 15)
    print("Bagged the following items\n  " +
        '\n  '.join(sorted(item for item,_,_ in bagged)))
    val, totalWeight = totalvalue(bagged)
    print("for a total value of %i and a total weight of %i" % (val, -totalWeight))

if __name__ == '__main__':
    main()