# Knapsack problem

class Item(object):

    def __init__(self, value, weight):
        self.value, self.weight = value, weight

items = [
    None,
    Item(4, 2),
    Item(5, 2),
    Item(2, 1),
    Item(8, 3),
]

# Weight of the knapsack
N = 5

cells = [[0] * (N+1) for i in xrange(len(items))]
for i, item in enumerate(items):
    for w in xrange(N+1):
        if item is None:
            cells[i][w] = 0
            continue

        c1, c2 = 0, 0
        if item.weight <= w:
            c1 = item.value
            if i > 0:
                c1 += cells[i - 1][w - item.weight]
        if i > 0:
            c2 = cells[i - 1][w]
        cells[i][w] = max(c1, c2)

print "\n".join(["\t".join(str(i) for i in inter) for inter in cells])

print "Max = %d" % cells[len(items) - 1][N]
w = N
for i, item in reversed(list(enumerate(items))):
    if item is None:
        continue
    if cells[i][w] > cells[i - 1][w]:
        print "  Selected: (%d, %d)" % (item.value, item.weight)
        w -= item.weight