背包问题是动态规划的一个经典例子，先介绍简单的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会提升效率。
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];
}
