动态规划--背包问题

背包问题

假设你要去野营。你有一个容量为6磅的背包，需要决定该携带下面的哪些东西。其中每样东西都有相应的价值，价值越大意味着越重要：
 水（重3磅，价值10）
 书（重1磅，价值3）
 食物（重2磅，价值9）
 夹克（重2磅，价值5）
 相机（重1磅，价值6）
请问携带哪些东西时价值最高？

算法思路

参考： 《算法图解》p142
Value = Max( v1, v2)
Value – 最高价值
v1 = 当前物品的价值 + 剩余空间的价值
v2 = 同样空间排除当前物品的价值

---

比如一共5种物品， 按顺序当前是“相机”，
Value[5,6] ：5种物品，空间为6磅。
v1 = 6 + Value[4,5]
相机的价值为 6
剩余空间为 6磅 - 1 磅 = 5 磅

v2 = Value[4,6]
在空间为6磅的情况下， 不选相机的最大价值。

---

代码实现

from copy import deepcopydef dynamic(gdict:dict, w:int):if len(gdict) == 1:k,its = gdict.popitem()n,v = its.popitem()if w >= n:return k,vreturn "",0else:k,its = gdict.popitem()n,v = its.popitem()newitem = deepcopy(gdict)if w>=n:name, s = dynamic(gdict, w-n)value = v +sres = "%s,%s"%(k,name)else:name,s = dynamic(gdict, w)value = sres = "%s"%namenewname,news = dynamic(newitem, w)if news > value:return newname, newsreturn res,valuegoods = dict()
goods["water"] = {3:10}
goods["book"] = {1:3}
goods["food"] = {2:9}
goods["jack"] = {2:5}
goods["camera"] = {1:6}
bags = 6print(dynamic(goods, bags))