【Python】0/1背包、动态规划

0/1背包问题：在能承受一定重量的背包中，放入重量不同，价值不同的几件物品，怎样放能让背包中物品的价值最大？

比如，有三件物品重量w,价值v分别是

w=[5,3,2]

v=[9,7,8]

包的容量是5，也就是我们要求得

maxVal=v1+v2+v3……

约束条件为：ws=w1+w2+w3……

我们的思路是，列举出所有可能的放入背包的选项，然后比较哪个价值大，这需要用到决策树。

决策树的思想是，用一组向量来描述当前的状态，比如 [当前考虑的物品i, 当前背包的空间w，当前已获得的价值v]，

决策树左儿子表示不选取当前物品np，右儿子表示选取当前物品p，首先递归到索引为最后一个的物品，然后回溯，每回溯到一个物品时候就比较选取当前物品和不选取当前物品哪个更有价值

 1 def maxVal(w, v, i, ws):
 2     if i == 0:
 3         if w[i] <= ws:
 4             return v[i]
 5         else:
 6             return 0
 7     without_i = maxVal(w, v, i-1, ws)#用递归算出不选取当前物品时候价值
 8     if w[i] > ws:
 9         return without_i
10     else:
11         with_i = maxVal(w, v, i-1, ws-w[i]) + v[i]#算出选取当前物品时候的价值
12     return max(without_i, with_i)
13 
14 
15 w = [5, 3, 2]
16 v = [9, 7, 8]
17 val = maxVal(w, v, 2, 5)
18 print(val)

这个方法可以正确运行，但是耗时为O(2^n)，所以当数据量增大时候，耗时会急剧增大，有什么办法可以减小耗时？同时列举出所有可能得出结论？

这就用到动态规划了

拿上面这个例子来说

当我们考虑第二个也就是最后一个物品的时候，我们需要把第0个，第1个物品要不要选取考虑一次

当我们考虑第一个儿子时候，也要把第零个物品要不要选取考虑一次

。。。

当物品非常多的时候，就造成了非常大的浪费

那么，我们能不能每次考虑一个物品之后，就把每种情况下的特征和值记录下来，以供以后考虑别的物品时候使用？

这就是动态规划

在这个背包问题中，我们可以使用(i,ws)来描述决策树中每种情况，同时保存对应的值。

 1 memo={}
 2 def maxVal(w, v, i, ws):
 3     try:
 4         return memo[(i,ws)]
 5     except KeyError:
 6         if i == 0:
 7             if w[i] <= ws:
 8                 memo[(i, ws)] = v[i]
 9                 return v[i]
10             else:
11                 memo[(i, ws)] = 0
12                 return 0
13         without_i = maxVal(w, v, i-1, ws)
14         if w[i] > ws:
15             memo[(i, ws)] = without_i
16             return without_i
17         else:
18             with_i = maxVal(w, v, i-1, ws-w[i]) + v[i]
19         res = max(without_i, with_i)
20         memo[(i, ws)] = res
21         return res
22 
23 w = [5, 3, 2]
24 v = [9, 7, 8]
25 val = maxVal(w, v, 2, 5)
26 print(val)