问题背景在一个风雨交加的黑夜，张三开启了亡命之徒的疯子模式：他背着一个可装载重量为W的背包到地主家里偷东西。楼主的房子有N件物品，每件物品都有重量和价值两个属性，其中第i件物品的重量为wt[i]，价值为val[i]。请问张三现在这个背包最多能装多少东西？例如：N=3//楼主有三样东西wt=[2,1,3]//每样东西的权重val=[4,2,3]//每样东西的价值W=4//的knapsackloadableweightalgorithm应该返回6。因为选择了第一项和第二项，如果重量不超过背包容量，则选择的值最大。如果每件物品只能选0或1（即要么把这件物品放进包里，要么不放进包里），这个问题叫做0-1背包问题；如果每个项目的数量没有限制，则称为无界（或满）背包问题。在今天的文章中，我们只关注0-1背包问题，下一篇会讲完整的背包问题。那我们如何选择要加载的项目呢？首先我们不考虑物美价廉的物品（不偷地主家的金银宝物珍珠首饰，拎出一袋煤...，那基本就saygoodbye了盗窃行业……）然后呢？然后考虑高质量高颜值的那个？还是质量较低、价值较低的那个？说明这件物品的“性价比”是最大的（也就是贪心算法，每次都选择当前最好的），那么这样能不能保证背包里的价值最好呢？先看一个例子：假设有5件物品，N=5，每件物品的质量和价值如下：W:20,30,40,50,60V:20,30,44,55,60V/W:1,1,1.1,1.1,1背包的容量为100，如果按照上面的策略：先选择“性价比”最大的：也就是背包的质量此时的第三项和第四项：40+50=90取值：44+55=99但是我们知道这道题比较好的选择策略是：此时选择第一、二、四项质量：20+30+50=100价值：20+30+55=105因此，我们的“性价比”是这种贪心策略显然不是最优策略。看过《理解动态规划》一文的读者会发现，在上一篇交换零钱的例子中，一开始我们也采用了贪心策略，但最后发现贪心并不是最优解，从而导致动态规划。没错，今天的题目是动态规划的又一个经典应用。解题思路根据前面的文章，我们知道动态规划的核心是：状态和状态转移方程。那么这个问题是什么状态呢？什么是状态？说白了，状态就是已知条件。重读题意，发现这道题只有两个已知条件：背包容量可选物品题要求在满足背包容量的前提下，能够装载的最大值。那么我们可以根据上面的状态定义dp数组，即：dp[i][w]表示：对于前i个物品，当前背包的容量为w，此时可以装载的最大值是dp[i][w]我们自然会考虑以下特殊情况：当i=0或w=0时，则：dp[0][...]=dp[...][0]=0解释：对于前0个物品，对于背包来说，无论背包容量等于多少，装载的值都是0；当背包容量为0时，无论装了多少物品（因为一个都装不下），背包里的值依然为0。根据这个定义，我们求的最终答案是dp[N][W].我们现在已经找到了状态，也找到了basecase，那么如何在状态之间转移（状态转移方程）呢？状态转移方程dp[i][w]表示：对于前i个物品，当前背包的容量为w，此时最大可装载的值为dp[i][w]。思考：对于当前第i个物品：如果第i个物品没有放入包中（第i个物品的质量大于当前背包容量）：那么显然，最大值dp[i][w]应该等于dp[i-1][w]，它没有加载，所以当前背包的总值等于之前的结果，即第i-1项之前的总值。如果第i个物品被装入包中，dp[i][w]应该等于多少？应该等于下面两个中的较大值：dp[i-1][w]//在i-1个物品之前，背包的最大值dp[i-1]w-wt[i]]+val[i]//我已经把第i个物品放进去了，所以此时背包的总价值即：当前第i个物品的价值val[i]+第i个物品之前，背包容量为w-wt[i]（w减去当前第i个物品的质量）dp[i-1]w-wt[i]]的值以上两个if可以写成如下code://如果第i个物品的质量大于当前背包容量if(wt[i]>W){dp[i][W]=dp[i-1][W];//继承上一个结果}else{//选择“上一个结果的值”和“当前第i个物品放入背包得到的值”之间数值较大的dp[i][W]=Math.max(dp[i-1][W],dp[i-1][W-wt[i]]+val[i])}例子，我们将使用另一个具体的例子来理解状态和状态转移方程。现在我们有4个项目。物品的价值和质量如上图左侧所示：6,42,51,48,1Step1我们先初始化一行一列为0，对应dp[0][w]和dp[i][0]。那么第一个问号应该填什么呢？我们根据上面的状态转移关系判断：第一个物品当前的重量为4>背包的容量，所以不能装，所以继承了之前的结果。最后的结果是什么？是第i-1项，即第0项，W=1时的值：if(wt[i]>W){dp[i][W]=dp[i-1][W];//继承前面的结果}此时方框里的值为0，所以第一个问号要填0。Step2现在到了背包容量W=2的时候，此时timethecurrent我（仍然是第一个项目）可以装进背包吗？我们发现4>2，此时还是放不下，所以也会继承之前的结果。最后的结果是i不变（还是第**0**项），W=2，所以结果还是0。现在第3步来到W=3，发现还是装不进去，所以填0。Step4下一步是W=4，此时物品的重量为4=4（背包的容量），可以装了。那么，根据之前的状态传递关系，应该是：else{//在“最后的结果值”和“把当前第i个物品装入背包中得到的值”中选择与较大的值dp[i][W]=Math.max(dp[i-1][W],dp[i-1][W-wt[i]]+val[i])}OptionA:Previousresult：dp[i-1][w]，即dp[0][4]=0选项B：将当前第i个物品放入背包中得到的值：dp[i-1]W-wt[i]]+val[i]此时第一个物品的重量为4，背包的容量为4，所以如果要放重量为4的这个物品，那么之前的容量背包的大小必须是当前背包容量-当前物品容量：4-4=0.然后我们在加载这个物品之前找到dp[i-1]W-wt[i]]=dp[0][0]=0（weight为4，value为6），则dp[i-1]W-wt[i]]+val[i]=0+6=660取最大值，所以这里要填问号在6Step5接下来我们来到W=5，这仍然是first项目，质量4<5（背包容量），我们可以放在里面。那么我们在选项A：之前的结果：dp[0][5]=0选项B：将当前第i件物品放入背包得到的值：dp[i-1]W-wt[i]]+val[i]此时第一个物品的重量为4，背包容量为5。因此，如果要装载这个重量为4的物品，那么背包之前的容量必须是：当前背包capacity-当前项目容量：5-4=1，我们在加载这个项目之前立即找到dp[i-1]W-wt[i]]=dp[0][1]=0（权重为4，值为6),然后dp[i-1]W-wt[i]]+val[i]=0+6=6选择一个最大值，也就是6，所以这里要填6。我们可以根据上面的状态传递关系，依次填入空白和其他值，最后我们得到整个dp数组：VW012345600000000064000066625000066614000066681088881414最后的dp[4][6]：考虑前四项，背包容量为6，能装的最大值就是想要的值（注：我们这里要找的是0-1背包问题，即某一项只能选0或1，不能选多于一个！）代码根据上面的思路，我们可以轻松写出代码：两层for循环外层循环i遍历项（即第几项）：for(inti=1;i<=N;i++){...}内层循环j遍历1~W（背包容量）之间的整数值：然后写状态转移方程为(intj=0;j<=W;j++){//外层循环i，如果第i个物品的质量为大于当前背包容量if(wt[i]>W){dp[i][W]=dp[i-1][W];//继承前面的结果}else{//在这两个“值上次结果”和“当前第i个物品放入背包得到的值”选择dp[i][W]=Math.max(dp[i-1][W],dp[i-1][W-wt[i]]+val[i])}}取更大的值由此我们给出完整的代码：classsolution{publicintknapsackProblem(int[]wt,int[]val,intsize){//定义dp数组int[][]dp=newint[wt.length][size];//对于加载的前0个item，存储在dp数组中的总值初始化为0for(inti=0;i
