声明

先粘一波代码，首先声明一下

这份代码是在 OI-wiki 的错误的示例代码 （错误有点多，我就不一一指出了） 上进行修改的，我知道有些人是从 OI-wiki 上跳转过来的，但是无奈于不会修改 OI-wiki ，所以在这里发一篇题解来帮助大家理解。

#include<bits/stdc++.h>
using namespace std; 
const int maxn = 13010;
int n,M, W[maxn], v[maxn], f[maxn];
int main() {
  cin>>n>>M;
  for (int i = 1; i <= n; i++) 
      cin >> W[i] >> v[i];
  for (int i = 1; i <= n; i++)
    for (int l = M; l >= W[i]; l--)
      if (f[l - W[i]] + v[i] > f[l]) f[l] = f[l - W[i]] + v[i];
  std::cout << f[M];
  return 0;
}

简述题目

有 n 个物品和一个容量为 W 的背包，每个物品有重量 wi 和价值 vi 两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。

思路

以下是错误思路（是部分背包问题的解法）

---

其实这道题我一开始想成贪心问题了，可能是因为小米的超高性价比手机感染了我 ~~（雷军：？？关我什么事~~~

我先计算出了每个物品的重量价值比（性价比），然后优先向背包内存放性价比高的物品，

然而后来我才意识到，，因为会产生很多情况，比如：

设背包最多可容纳50kg的重量

物品	重量(kg)	价值	性价比
A	10	60	6
B	20	100	5
C	30	120	4

按照贪心，单位重量的价值排序：A > B > C

最终贪心选择的结果是这样的：物品 A 全部拿完，物品 B 也全部拿完，物品 C 拿走10Kg（只拿走了物品 C 的一部分！！！） 如果要必须符合条件，则只能拿 A,B 物品，总价值就是160，

但是显然，我们会发现一种更高价值的情况：如果拿物品 B 和物品 C ，得到的价值为220。所以说贪心不适合用于这种背包问题，那么如何求解呢？

以下是 0-1 背包的正确解法

设 DP 状态 $f_{i,j}$ 为在只能放前 $i$ 个物品的情况下，容量为 $j$ 的背包所能达到的最大总价值。

考虑转移。假设当前已经处理好了前 $i-1$ 个物品的所有状态，那么对于第 $i$ 个物品，当其不放入背包时，背包的剩余容量不变，背包中物品的总价值也不变，故这种情况的最大价值为 $f_{i-1,j}$ ；当其放入背包时，背包的剩余容量会减小 $w_{i}$ ，背包中物品的总价值会增大 ，故这种情况的最大价值为 $f_{i-1,j-w_{i}}+v_{i}$ 。

由此可以得出状态转移方程： $$f_{i,j}=max(f_{i-1,j},f_{i-1,j-w_{i}}+v_{i})$$ 在程序实现的时候，由于对当前状态有影响的只有 $f_{i-1}$ ，故可以去掉第一维，直接用 $f_{i}$ 来表示处理到当前物品时背包容量为 $i$ 的最大价值，得出以下方程： $$f_{i}=max(f_{i},f_{i-w_{i}}+v_{i})$$

务必牢记并理解这个转移方程，因为大部分背包问题的转移方程都是在此基础上推导出来的。