4.动态规划 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 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 w = [5, 3, 2]
23 v = [9, 7, 8]
24 val = maxVal(w, v, 2, 5)
25 print(val)
参考博客：https://www.cnblogs.com/fcyworld/p/6243012.html
5.0/1背包问题练习
def maxVal(toConsider, avail):
if toConsider == [] or avail == 0:
result = (0, ())
elif toConsider[0].getWeight() > avail:
#查询右侧分支
result = maxVal(toConsider[1:], avail)
else:
nextItem = toConsider[0]
#查询左侧分支
withVal, withToTake = maxVal(toConsider[1:],
avail - nextItem.getWeight())
withVal += nextItem.getValue()
#查询右侧分支
withoutVal, withoutToTake = maxVal(toConsider[1:], avail)
#选择更好的分支
if withVal > withoutVal:
result = (withVal, withToTake + (nextItem,))
else:
result = (withoutVal, withoutToTake)
return result
