我们在上一篇文章已经对动态规划的算法思想有了一定的了解，今天我们再来通过一个经典问题：0，1背包问题，从更深层次的角度来认识一下动态规划算法。建议先看上一篇文章，再来看这篇。
首先，我们来看一下什么是0，1背包问题。
问题描述：给定 n 件物品，物品的重量分别为w1、w2、w3....,现需要挑选物品放入背包中，假定背包能承受的最大重量为V，问应该如何选择装入背包中的物品，使得装入背包中物品的的重量最大？
首先，我们最直观的想法就是，穷举所有可能的装法，然后从中选出满足条件的最大值。我们可以使用回溯算法来实现。如下所示：
class BagQ: #假设物品的重量都大于0 #背包的最大承重也大于0 maxW=0 weight=[2,2,8,3,5,3] #物品重量 n=6 #物品个数 w=10 #背包的最大承重 def getMax(self,i,cw): if cw==self.w or i==self.n: #背包装满或者物品被考察完了 if cw>self.maxW: self.maxW=cw return self.getMax(i+1,cw) #第i个物品不放入背包 #考察放入第i个物品后，会不会超过背包的容量 if cw+self.weight[i]<=self.w: self.getMax(i+1,cw+self.weight[i]) #选择装第i个物品 bag=BagQ() bag.getMax(0,0) print(bag.maxW)