0|0,1背包问题 0|1背包问题

背包问题是动态规划的一个经典例子，先介绍简单的0，1背包问题。
参考：http://www.acmerblog.com/dp-10-01-knapsack-problem-5502.html

在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2……Wn，与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案。

注意：在本题中，所有的体积值均为整数。01的意思是，每个物品都是一个整体，要么整个都要，要么都不要。
和之前的问题一样，不管你是用递归还是用动态规划，分析出关系式是最重要的。
每个物品只有放入和不放入两种可能。我们从这里入手分析第n个物品的情况。

如果第n个物品的体积太大，Wn>W，那么就不需要放进去了
如果放进去，那么总价值应该加上当前物品的价值，剩余空间减小；
如果不放进去，那么总价值和空间都不变，只是总的物品-1.

我们对后两种情况求max就可以了。
递归解决：首先呢，我们直观的使用递归来写：
我们传递进去总重量，总数量，以及体积表和价值表，返回最大价值。

//1,recursive int solution_r(int* w,int weight,int* p,int n) { if(w==0||n<=0||!p) return 0; if(w[n-1]>weight) return solution_r(w,weight,p,n-1); else return maxOfTwo(solution_r(w,weight-w[n-1],p,n-1)+p[n-1],solution_r(w,weight,p,n-1)); }

动态规划：为什么要使用动态规划呢？
看下图，使用递归的时候进行了很多次重复的计算！

文章图片
递归的过程并且这个问题符合动态规划的两个特征：(重叠子问题和最优子结构)
所以，我们使用DP会提升效率。
【0|0,1背包问题】DP的思路还是和之前的一样，保存前面的计算结果。
我们申请一个dp的二维矩阵，因为我们有两个维度的信息在变化。
在上面的递归函数里面，虽然我们传递了4个参数，但是有两个是不变化的，所以我们只需要二维的矩阵，分别代表当前是第几个物品（i）和当前剩下的空间（j）。
但是下面的程序里面，有一些角标的细节需要大家注意一下，看注释就好。

//2,dynamic programming //in solution1, we just changed two parameters int solution_dp(int* w,int weight,int* p,int n) { if(!w||!p||n<=0) return 0; int dp[100][100]; //dp[n][weight] memset(dp,0,sizeof(dp)); int i=0,j=0; //j is the remaining weight,i is the ith item for(i=1; i<=n; i++)//i<=n,since we have n items { for(j=1; j<=weight; j++) {if(w[i-1]<=j)//but why w[i-1]?----->in array,it is actually i-1 to ith item dp[i][j]=maxOfTwo(dp[i-1][j-w[i-1]]+p[i-1],dp[i-1][j]); else dp[i][j]=dp[i-1][j]; } } return dp[n][weight]; }