DP solution to the knapsack problem

Dynamic programming (DP) is a fancy name for using divide-and-conquer technique with a table. In this snippet, DP is used to solve the Knapsack Problem.

objects = [
    #(cost,weight,[object])
    (1,4,[1]),
    (4,5,[2]),
    (3,8,[3]),
    (7,3,[4]),
    (4,30,[5]),
    (2,1,[6]),
    (8,8,[7]),
    (12,2,[8]),
    
]

def DP_KP( S=objects, limit=16 ):
    TRIPLE = [(0,0,[]),S[0]]
    for i in range(0,len(S)-1):
        new = {}
        for k, w, SET in TRIPLE:
            weight =  w + S[i+1][1]
            if weight <= limit:
                cost = k + S[i+1][0]
                if cost in new.keys() and weight >= new[cost]: pass
                else: new[cost] = ( cost, weight, SET + S[i+1][2])
        TRIPLE.extend(new.values())
    return TRIPLE

print 'Cost: %s, weight: %s, objects:%s' % DP_KP()[-1]

Google