knapsack algorithm applied to Girl Scout cookies

gs_knapsack.py

from itertools import groupby
 
try:
        xrange
except:
        xrange = range
maxwt = 80

#weight, weight, value to me 
groupeditems = (
        ("do-si-does", 8, 20, 4),
        ("samoas", 7, 15, 5),
        ("savannah smiles", 25, 150, 1),
        ("tagalongs", 15, 7, 6),
        ("thin mints", 32, 10, 2),
        ("trefoils", 44, 10, 3),)

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
print("Bagged the following %i items\n  " % len(bagged) +
      '\n  '.join('%i of: %s' % (len(list(grp)), item[0])
      for item,grp in groupby(sorted(bagged))))
print("for a total count of %i and a total weight of %i\n" % (
     sum(item[2] for item in bagged), sum(item[1] for item in bagged)))

print("total cost is %i" % (len(bagged) * 4))