嘿，背包问题可不只是个野营的烦恼，它简直就是生活中的“选择困难症”的终极考验！想象一下，你手里只有6磅的背包，却要装下所有你觉得“必须带”的东西。水、食物、书、夹克、相机，每样都看似不可或缺，但空间有限，怎么办？

这就是动态规划的魔法时刻！它的核心思想就是：别贪心，一步步来。比如，相机值6分，但如果你不带它，剩下的5磅能装下什么？是不是比带相机更值？这就是算法的精髓——权衡取舍，选择最优解。

代码实现当然更酷了！通过递归的方式，不断比较“带”和“不带”的收益，最终找到最大价值组合。想象一下，如果生活也能用Python跑一遍，咱是不是能少点纠结？不过话说回来，背包问题可不只是算法题，它还能用来优化资源配置、时间管理，甚至投资组合。所以，下次遇到“选择困难症”，不妨试试动态规划的思路，或许能帮你找到最优解！

最后，别忘了问问自己：如果真的只能带6磅的东西，你最舍不得丢的是什么？这个问题的答案，可能比算法本身更有趣哦！

背包问题

假设你要去野营。你有一个容量为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))