dynamic programming generic 0-1 knapsack problem solver

knapsack.py

def solve_knapsack(items, maxcost, cost=lambda n:n, value=None):
    """
    Generic dynamic-programming knapsack problem solver. Takes time
    O(len(items) * maxcost), so it can be helpful to reduce the costs
    and maxcost by the greatest common divisor if possible. Costs for
    all items must be nonnegative integers.

    Returns the set of items the sum of whose costs does not exceed
    maxcost, and the sum of whose values is otherwise maximal.
    """

    if value is None:
        value = cost

    items_ann = [(item, cost(item), value(item)) for item in items]
    table = [[0] * (maxcost + 1) for row in xrange(len(items) + 1)]

    for table_index, (i, cost, val) in enumerate(items_ann):
        lastcost = table[table_index]
        thiscost = table[table_index + 1]
        for cap_index in xrange(maxcost + 1):
            if cost > cap_index:
                newcost = lastcost[cap_index]
            else:
                newcost = max(lastcost[cap_index], val + lastcost[cap_index - cost])
            thiscost[cap_index] = newcost

    result = []
    ctr = maxcost
    for table_index, (item, cost, val) in reversed(list(enumerate(items_ann))):
        if table[table_index + 1][ctr] != table[table_index][ctr]:
            result.append(item)
            ctr -= cost

    return result[::-1]