10.5.2 0-1背包问题
0-1背包问题，指将给定物品存储到指定的一个背包里，要么被选择（1），要么不被选择（0）。著名的0-1背包问题，可以通过动态规划算法来实现。如表10.2所示，需要挑选累加和价格最高的几个物品放到体积为9的背包里。
表10.2 物品特征清单
1.解题思路
根据动态规划解题思路，可以把求解过程分为最小子解，看看1体积背包最优解是几个物品价格的组合；然后在1体积最优解的基础上，求2体积背包的最优解是几个物品价格的组合；依次类推，最后推算出9体积背包的最优解。
最优解的求解过程，需要通过二维表做记录，方便后续步骤直接使用，避免反复计算，其记录表格设计如表10.3所示。其中i代表第i个物品（对应表10.3行位置），j代表背包分解的体积大小（对应表10.3列的位置）。
表10.3 0-1背包动态规划求解记录
为了动态规划依据前一决策结果，表10.3的第0体积列第0行作为求当前值辅助，没有其他实质意义。
在表10.3的基础上，借助动态规划解答思路，可以人工推理求解如下。
第一步，求1号物品（体积为5，价格为5），在1体积，2体积，…，9体积依次递推求解的情况下，得到的结果为0，0，0，0（1体积到4体积情况下，无法装入1号物品），5体积到9体积情况下都可以装入1号物品，其对应填写价格都为5。
第二步，求先装入2号物品（体积为2，价格为6）的情况（再考虑与1号物品的组合），能否依次被1体积到9体积装入；求解为1体积无法装入，上一行最优解为0（i-1，j），则（i，j）处也填写0；2体积到6体积情况下，刚好可以装入2号物品，填写价格为6；7号物品到9号物品情况下，除了装入2号物品外，还可以装入1号物品，以2号物品对应的7体积为例，2号物品5体积小于7体积，可以装入该物品，于是判断上一行最优解的坐标（i-1，j-w）=（1，7-2）对应的最优解价值为5，则在5价值的基础上加当前物品的价值6合计为11（装入新物品），若不装入，则意味只能装入1号物品，其价值为5，两个值取大者，则第二步最优解为11。(https://www.daowen.com)
第三步，求3号物品装入情况……
第四步，求4号物品装入情况……
由此，在物品装入过程中，需要做两种状态的比较：
（1）当前需要装入的物品体积大于背包空间（v[i]＞j）时：
当前位置的价格为V（i，j）=V（i-1，j），即当前（i）物品与上一行（i-1）物品对应j位置的物品存放价格一样；
（2）当前需要装入的物品体积不大于背包剩余空间（v[i]＜=j）时：
背包还有足够的空间装入当前物品，但是不一定是最优解，所以需要在装与不装之间选择一个最大值：V（i，j）=max｛V（i-1，j），v（i）+V（i-1，jw（i））｝，其中V（i-1，j-w（i））为上一行最优解，v（i）为i行当前物品的价格。
2.代码实现
代码文件：10_5_2_01napsack.py
上述代码执行结果如下：
