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]