题面
有N件物品和一个容量为M的背包。第I件物品的重量是W[i],价值是D[i].
求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
样例数据
输入
4 6
1 4
2 6
3 12
2 7
输出
23
分析
（如果亲爱的读者对动态规划略有了解的话应该能看出来这是个01背包的板子题吧）暴力枚举就别想了哈，过不了的（嘻嘻）
1. 动态规划基本思想
将一个复杂问题拆成很多子问题，算出每一步的最优解，之后将每一步的合在一起
动态规划和贪心算法有点相似 下面我们通过一个简单的例题来区分一下
如下图，找出从最上面一层到最下面一层的最长路径，只能向下走（节点编号用蓝色写出，每条路的值用暗红色写出）
贪心：
从节点开始，找能走的边中最大的，重复前面的这个步骤，直到走到最下面一层,答案是10
（路线：节点1 ——> 节点3 ——> 节点5 ——> 节点9)
动态规划：
动态规划是从最后向前搜索的（这也是和贪心的最大区别）
上面这句有点个抽象 啥意思呢
就是说动态规划先从倒数第二层开始，
举个例子，
从节点4开始向下走，那要走哪条边呢？
当然是权值较大的了！
那选出来的边咋办呢？
记在节点上
就是说，给节点4赋予一个值，这个值是这个点向下所走的路的边权的总和。（因为举得节点4的例子里面节点4只能向下走一层就到头了，所以这个节点4 记的就是从节点4通往节点7的这条路的值，就是8）
以此类推，节点5的值是3，节点6的值是6
这是倒数第二层了，接下来向上搜索倒数第三层
依然是向上面说的那种方法，不同点就是要加上倒数第三层所到达的倒数第二层的节点被赋予的值
举个例子
对于节点2来说，能走的路有一条值为4的和一条值为9的，要选的是权值为9的那条
那按照上面讲述的倒数第二层的方法是不是应该让节点2的值为9呢？
并不是
节点2被赋予的值应该是 12（要选择路的权值与选择此路到达节点被赋予的值，选择和最大的）
这样一来，节点2被赋予的值就记录了从节点2走到最后一层的最大路线
（这次为什么不能选最大路线呢？因为选择了由上层向低层最大的路，并不能保证这一步被选择的节点接下来能走的路也最大）
（如下图）
以此类推，最后节点4为8，节点5为3，节点6为6，节点2为12，节点3为8，节点1为13
看到这里应该清楚01背包的思想了吧（虽然我有点啰嗦）
接下来如何码出来呢？
我们需要依靠一个东西，叫递推式
2.递推式
（先看题，看了这么久，想必大家已经把题面忘了 嘻嘻）
有N件物品和一个容量为M的背包。第I件物品的重量是W[i],价值是D[i].
求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
这道题中的递推式是
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + d[i]);
大家一定会产生几个问题这个i是什么？这个j是什么？
先笼统解释一下：i表示物品个数，j表示容量。
这个式子可以大概翻译一下：d[i][j]等于
在0i-1个物品中选取第i个物品（大概意思就是不将第i个物品加入背包，因为0i中根本就不包括第i个物品，根本选不了）
或者在确定了0~i-1个物品的最优选法后，选取第i个物品，
以上两个方案中的最优情况。（为啥用max呢？因为题目中要求最大值）。
这个[j-w[i]]表示的是背包中剩余的空间。
如果看不懂的话，可以看这位大佬的https://zhuanlan.zhihu.com/p/345364527
我在下面复制了这位大佬的一段，希望对大家理解有帮助：
确定dp数组以及下标的含义
对于背包问题，有一种写法， 是使用二维数组，即dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
要时刻记着这个dp数组的含义，下面的一些步骤都围绕这dp数组的含义进行的，如果哪里看懵了，就来回顾一下i代表什么，j又代表什么。
确定递推公式
再回顾一下dp[i][j]的含义：从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
那么可以有两个方向推出来dp[i][j]，
由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]
由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值
所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
废了好大劲，but还没完，因为如果写这样的二维数组会崩空间（想不到吧 嘻嘻）
3.优化成省空间的一维数组
回顾前面的递推式
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + d[i]);
我们发现，如果把dp[i-1]层的变成d[i]层的，好像也是可以的哦？
那么，这个式子就变成了dp[i][j]=max(dp[i][j],dp[i][j-w[i]]+d[i]);
那这看上去都是dp[i]层的，那这个i是不是就没用了呢？对，就是没用了
于是可得
dp[j]=max(dp[j],dp[j-w[i]]+d[i]);
大功告成，上代码（我在这里用的字母是a,个人习惯，把字母dp全换成a就好了）
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
int w[5000],d[5000],a[50000];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>w[i]>>d[i];
}
for(int i=1;i<=n;i++)
{
for(int j=m;j>=w[i];j--)
{
a[j]=max(a[j-w[i]]+d[i],a[j]);
}
}
cout<<a[m];
return 0;
}
膜拜大佬https://zhuanlan.zhihu.com/p/345364527写得太好了，太清楚了，看懂了。
最后祝大家学习快乐（嘻嘻）
标签：背包,洛谷,容量,题解,max,物品,例题,节点,dp From： https://www.cnblogs.com/a-good-cat-001/p/18403347