defbacktracking_bag(i, cw, items): global max_weight,methods """ i: test the item i cw: current total weight weights: the weight of items W: total weight the bag can load n: the number of items max_weight: the max weight the bag can load """ if i == n: if cw <= W and cw >= max_weight: if cw > max_weight: max_weight = cw methods = [] methods.append(items[:]) else: methods.append(items[:]) return
defbacktracking_memory_bag(i, cw, items): global max_weight,methods,memory """ i: test the item i cw: current total weight weights: the weight of items W: total weight the bag can load n: the number of items max_weight: the max weight the bag can load """ if i == n: if cw <= W and cw >= max_weight: if cw > max_weight: max_weight = cw methods = [] methods.append(items[:]) else: methods.append(items[:]) return
if memory[i][cw]: return memory[i][cw] = True# remember the state of i
for i inrange(1,n): for j inrange(W): ## 不把 i 放入背包中,当前背包重量不变 if dp[i-1][j]: dp[i][j] = 1
for j inrange(W): ## 把 i 放入背包中 if j + weights[i] <= W and dp[i-1][j]: dp[i][j+weights[i]] = 1 pprint.pprint(dp) for i inrange(W,-1,-1): if dp[-1][i]: return i