本文讲述经典算法——动态规划的 常见问题01背包
一篇文章带你学会01背包问题，妈妈再也不担心我遇到01背包了！！！
问题描述
有n个物品，它们有各自的体积和价值，现有给定容量m的背包，如何让背包里装入的物品具有最大的价值总和？
每种物品只有放入和不放入这两种状态，因此叫做01背包问题
为方便讲解和理解，下面讲述的例子均先用具体的数字代入，即：eg：n=4,m=6
由于样例数据量小，我们很容易可以看出来最优的选择为物品3+物品4+物品1
总重量=3+2+1=6 总价值=12+7+4=23 这就是最优解；
有的人可能会有疑惑，可以用贪心吗？ 答案是 不可以；
因为选取单个价值最高并不能保证最终的总价值是最高的，也许有一个体积比它小很多，价值相差不大的呢，这样不就没选它了嘛。
动态规划问题的本质
本质就是穷举？递归？递推？
Q1：如何穷举？
写出状态转移方程，暴力穷举所有可行解。
Q2：如何聪明地穷举？
用备忘录消除重叠子问题，写出自顶向下的解法；
进一步，可以写出自底向上的迭代递推的解法；
再进一步，可能可以优化空间复杂度
动态规划问题的解题思路分析
1、通过问题描述，时间状态、选择、定义这几部框架
2、写状态状态转移方程
3、一眼看出是否存在重叠子问题
4、确定dp数组的遍历顺序
针对该问题，我们来看一看具体的步骤是怎样的。
根据第一步 状态有：装入物品数量、背包容量，所以确定我们的dp数组是二维的
一定要清楚的明白dp数组代表的含义，才能顺利地写出状态转移方程！这一点很重要！！！
首先看第二个情况，不把物品放进背包的最大价值
不放第 i 个物品，不就意味着，最大价值就等于 前 i-1个物品的最大价值嘛
所以 dp[i][w] = dp[i - 1][w];
--------------------------------------------------------------------------------------------------------------------
然后再看比较复杂一点的第一种情况，将物品放进背包的最大价值
这种情况下，我们存放结果情况显然不变，依然是i个物品放w容量，所以前面还是dp[i][w]
那么=后面的结果呢？
就是前面 i-1 个物品，在容量为 w-当前物品重量的情况下 ，加上 第 i 件物品的价值！悟了吧
所以 dp[i][w] = dp[i -1][w - wp[i].wei] + wp[i].val;
----------------------------------------------------------------------------------------------------------------------
然后，我们应该分情况，当该物品能够被放进去才进行计算
否则就和没有放入的结果一样。
相信你看到这里已经很有感触了，我们来看看代码是怎么实现的吧。
#include<bits/stdc++.h>using namespace std;struct wupin{int wei;int val;}wp[3405];int dp[3500][13000];int main(){int n,m; //n种物品，容量mcin>>n>>m;for(int i = 1;i <= n;i++) cin>>wp[i].wei>>wp[i].val;for(int i = 1;i <= n;i++){ // i 代表 前i个物品for(int j = 1;j <= m;j++){ // j 代表 背包容量为 j 时if(wp[i].wei > j){dp[i][j] = dp[i-1][j];}else{dp[i][j] = max(dp[i-1][j], dp[i-1][j-wp[i].wei] + wp[i].val);}}}cout<<dp[n][m]<<endl;return 0;}
结合上述思路，是不是已经理解了呢？
这里有一个问题，就是当数据量比较大时，比如代码中的n=3500，m=13000时，会消耗巨大的内存，大概是180MB，这会超过大多数OJ的内存限制，比如北大OJ(POJ 4131)，用上述代码就超过内存限制了！
如何解决这一问题呢？
在这里我们使用滚动数组的方式就可以解决了！
这里给出代码，稍有不同的是，该题滚动数组方式采用从右往左的顺序求值
#include<bits/stdc++.h>using namespace std;struct wupin{int wei;int val;}wp[3405];int dp[13000]={0};int main(){int n,m; //n种物品，容量mcin>>n>>m;for(int i=1;i<=n;i++)cin>>wp[i].wei>>wp[i].val;for(int i=1;i<=n;i++){ // i 代表 前i个物品for(int j=m;j>=0;j--){ // j 代表 背包容量为 j 时if(wp[i].wei<=j){dp[j] = max(dp[j],dp[j-wp[i].wei]+wp[i].val);}}}cout<<dp[m]<<endl;return 0;}
这样代码就AC啦！！！
至此，01背包问题已经讲述完了，如果有什么不明白的地方或是文章存在一些问题，欢迎coder在下方留言。
