不少0输入样例输出：接下来有N行,每行整数

作为动态规划模型中的经典模型。它不仅简单易懂，而且可以在一定程度上揭示动态规划的本质，所以很多教材都把它作为动态规划的第一个例子。

题目要求

有 N 个物品和一个容量为 V 的背包。第 i 个物品的成本是 c[i]，价值是 w[i]。找出要放入背包的物品，使这些物品的成本之和不超过背包的容量，并且价值之和最大。

输入格式

第一行，两个整数，用 N 和 M 空格隔开，分别代表物品的数量和背包的体积。

接下来有N行，每行有两个整数vi，wi，用空格隔开，分别代表第i个商品的数量和价格

输出格式

输出一个表示最大值的整数。

数据范围

0 输入样本

4 5
1 2
2 4
3 4
4 5

样本输出：

8

分析过程

0/1背包问题是最基本的背包问题，每个物品最多只能放置一次或选择不放置。

思路A：一共有n件物品，背包容量为m。对于每一项，我们有两个选项，一项有两种类型，两项有四种类型，三项有八种类型，那么n项就有2^n个方案。穷尽这2^n个方案，当n=100时，多少相等？2 的百次方等于：1.26*10^30 这个值很大。比如有一张可以完全折叠的纸，厚度为0.1mm，对折一次，那么厚度为0.2mm贪心算法 背包问题 c，然后再对折一次，就是0.4mm…以此类推，对折n次，那么纸的厚度为：(2^n)×0.1mm 这个厚度宇宙的增长会成倍增长，那么折叠100次后，它的长度将达到“134亿光年”，而大爆炸以来的整个时间只有137亿年。这太过分了，只是为了表明这种详尽的方法是不可取的。

思路B：动态规划的本质是寻找递归表达式。寻找递归表达式时必须有一定的边界限制（如青蛙跳步，没有限制）

那么这个问题给出了一个边界限制：容量M，当容量满了就不能再放下东西了，所以我们在进行递归的时候需要考虑当前的容量，这就是我们的约束目标函数是什么？目标函数是最大化我们的值 max(value)

这个递归函数怎么写？我打算使用一维数组来解决这个问题。我首先初始化了一个名为 f 的数组，长度为 m+1（对于从 1-m 开始的索引来表示从 1-m 开始的容量），最后取 f 的最后一个元素就是答案。那么这个递归函数可以表示为 f(m)=max(f(m), f(mw[i])+v[i])

f(m) 当前背包容量为m时不选择当前物品

f(mw[i])+v[i] 当前背包容量为m时选择当前物品

mw[i] 表示我的背包在最后一次选择中必须至少给我留出 w[i] 个空间，这样我才能选择当前项，然后得到它的值 v[i]

问题解决步骤

首先初始化f，将权重放入数组W(weighted)，将值放入数组V(value)

接下来，我开始遍历我的物品，一共n个物品。在遍历我的每件物品时，我会增加我的背包容量（从 1 到 m）。这一步是什么意思？我们举一个容量从1开始递增的例子，假设第一项的权重为1，value=2，那么当容量为1时，f[1]=2，当容量为2时，f[2] =4 f[3]=6 …？？？好像进错片场了。我们的问题的前提是每个项目只能选择一次或不选择以最大化收益，那么如果背包的容量从1一直增加，我们的问题就变成了每个项目可以选择多次。

为什么会出现这种情况，因为如果背包的容量从少到多，它会认为每次对max()都贪婪，我可以多放一些这个物品，现在我放一个贪心算法 背包问题 c，可以吗？再放一张。

如何修改？将容量从 m 减少到 1 就足够了。 f[m]=2,f[m-1]=2…f[1]=2 在这种情况下，因为背包容量从更多to少，每次对max()贪心，都是看能不能先放下一个当前的item，不会有超过两个item可以放下的情况。

最后，我们输出 f 并取最后一个元素。

注意：区别实际上在 f[mw[i]]，

如果容量从小到大遍历，最终f[m]的结果不取决于前一个item的选择，而是取决于当前item的选择

如果容量是从大到小遍历，那么最终的f[m]取决于前面item选择的结果

c++ 实现

#include
using namespace std;
const int N=1010;
int f[N];
int v[N],w[N];
int n,m;
int main(){
    cin>>n>>m;
    for(int i=0;i>v[i]>>w[i];
    }
    for(int i=0;i=v[i];j--){
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<