01故事的起源有个背包，容量有限，容量为w，有m个物品可供选择，每个物品只有一个。每件物品都有一定的重量和价值，那么选择将哪些物品放入背包中才能使所选物品的总价值最大化呢？02问题分析如果背包没有容量限制，那么一定是可以用到背包里所有物品中最有价值的东西。但是现在背包比较小，只能选择把一部分放在背包里。比如里面只能放一个，所以里面可以放钻石。很容易想到重量小单价高的物品尽量放，但是如何对问题进行严谨的建模，继续分析。03分析背包有固定的容量，1kg，2kg，3kg。事实上，具体数量对问题的本质没有影响。对于物品，有两种情况，要么放在背包里，要么不放。如果有m个物品，一共有2^m种选择方法。显然，这个数字非常大，不可能直接列举出所有的选择方法。04小问题就是大问题假设背包的容量是1kg，最大可以装的就是手表，其他的都装不下。如果有一个更大的背包，它的容量可以看作是2个容量较小的背包的总和。但是它所能容纳的价值不能简单的分解成两个小背包，因为只有一个物品，会导致物品重复。于是，再次对物品进行划分，m件物品可以分解为m1+m2，背包容量也可以分解为w1+w2。看上面左右两边，还是和原来的问题一样，本质还是一样，只是变成了数据规模更小的子问题。如果子问题有答案，是否可以组合成一个更大范围的答案？我估计这里有同学会说，这样分解出来的小问题一定能得到最终大问题的最优解吧？我们试着证明一下。05逆向思维假设以下几项是最终的最优解选择。如果从某个位置切一把刀，保证w1和w2能把最终的选择项拿在自己这边，那么最优解就分成了两个小规模问题的最优解。这也说明，如果枚举出小规模最优解的所有组合，还必须得到大规模最优解。06算法建模根据上面的分析，现在问题变的简单了，直接把小问题按照item和权重拆分，通过小问题推导出大问题即可。设f[i][j]表示前i个物品的背包容量为j时可以选取的最大值。w[i]代表第i个物品的重量，v[i]代表第i个物品的价值。如果第i项放不下，则f[i][j]=f[i-1][j]可以放第i项，则f[i][j]=max(f[i][j],f[i-1][j-w[i]]+v[i])那为什么只需要从第i-1项开始递归呢，因为只要一个case就可以得到最优解，就是没有必要一一列举前面的所有部门。这其实相当于把i项分成i-1项和1项。先前的子问题也已包含在当前解决方案中。代码实现intf[101][1001],w[101],v[101];intn,m;intmain(){cin>>m>>n;for(inti=1;i<=m;++i){cin>>w[i]>>v[i];}f[0][0]=0;for(inti=1;i<=m;++i){for(intj=0;j<=n;++j){f[i][j]=f[i-1][j];if(j>=w[i]){f[i][j]=max(f[i][j],f[i-1][j-w[i]]+v[i]);}}}cout<
