关于背包：
背包的本质是每一个物品或动作对当前所有状态的更新
板子：
- 01背包：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
for (int i = 1; i <= n; i ++ )
for (int j = m; j >= v[i]; j -- )
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m] << endl;
return 0;
}
01背包的问题是：给定一个容量为 $V$ 的背包，有 $N$ 个物品，每个物品有一个价值 $v_i$ 和重量 $w_i$ ，求在所有物品重量不超过 $V$ 的前提下的能获得的最大价值为多少。
首先不难发现，题目的选法相当灵活（约束条件弱），而且很难直接考虑最优解的选法，所以我们尝试通过不断决策来求出最优解。
如果直接考虑每一种选法，那么选定物品的方案会有相当多的可能性——考虑所有没有选的物品，会带来相当多的决策数，为了减少决策的数量，我们想每次只决策一个物品选与不选。
为了便于递推，我们从 $1$ 到 $N$ 逐个枚举所有的物品，每次只决策当前的物品选与不选，并从前面的状态递推当前的物品选不选。
然而我们还有第二个约束条件 $V$ ，每次都要考虑选取当前的物品对后面所有决策的影响（背包的本质），那么不妨将剩余空间也纳入我们的考量之中。从而有：
$$
f_{i,j} \ = \ max( \ f_{i-1,j-v_i} \ + \ w_i \ , \ f_{i-1,j} \ )
$$
其中，$f_{i,j}$ 表示的是只选前 $i$ 个物品，剩余的空间为 $j$ 的最大价值。
那么剩余空间怎么迭代？只要从 $0$ 到 $V$ 枚举所有可能的取值即可。
优化：
经过对运算过程中产生的 $f$ 这张表进行观察，可以发现：
1.每次我们迭代 $i$ 只用到了 $i-1$ 这一层的值
2.每次迭代 $j$ ，我们都只用到了 $j-v[i]$ 和 $j$
那么，我们猜想：可以直接删掉 $i$ 这一维，单用 $j$ 这一维自己刷新自己的值。
然而我们发现有一个问题：
在更新 $f_{j + v_i}$ 时，用于更新其的 $f_j$ 已经被更新过了，所以会导致错误
这个问题在我们重新考虑 $i$ 维时很容易就发现其问题所在：
$f_j$ 经过更新，已经是它处于第 $i$ 层的值了，然而 $f_{j + v_i}$ 仍然是第 $i-1$ 层的状态，要用 $i - 1$ 层的值来更新，也就是我们用第 $i$ 层的值参与了第 $i-1$ 层的更新，自然导致了问题。
进一步分析我们会发现这个问题发生的原因是：从前向后更新（用$f_{i-1,j-v_i}$ 和 $f_{i-1,j}$，$j-v_i<j\le j$），导致前面的点先于后面被更新，也就有了上面的错误，解决方法是从后向前更新，也就有了上面代码的 for (int j = m; j >= v[i]; j -- )
2.完全背包：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
for (int i = 1; i <= n; i ++ )
for (int j = v[i]; j <= m; j ++ )
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m] << endl;
return 0;
}
完全背包在01背包的基础上更改了一个条件：每个物品可以选无穷多个
考虑一个问题：为什么01背包中，我们要用 $i-1$ 层来更新 $i$ 层？
答案是，01背包中同一个物品不能重复选，如果用 $i$ 层的值更新 $i$ 层，相当于第 $i$ 个物品被选了多次（错误写法），所以要用 $i-1$ 层更新 $i$ 层。
可以发现，由于每个物品只能选一次的约束被去掉了，所以用 $i$ 层更新 $i$ 层的想法是被允许的，从而，正序更新就是这题的正解。
3.多重背包：
//无优化
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
for (int i = 1; i <= n; i ++ )
for (int j = v[i]; j <= m; j ++ )
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m] << endl;
return 0;
}
//带优化
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 12010, M = 2010;
int n, m;
int v[N], w[N];
int f[M];
int main()
{
cin >> n >> m;
int cnt = 0;
for (int i = 1; i <= n; i ++ )
{
int a, b, s;
cin >> a >> b >> s;
int k = 1;
while (k <= s)
{
cnt ++ ;
v[cnt] = a * k;
w[cnt] = b * k;
s -= k;
k *= 2;
}
if (s > 0)
{
cnt ++ ;
v[cnt] = a * s;
w[cnt] = b * s;
}
}
n = cnt;
for (int i = 1; i <= n; i ++ )
for (int j = m; j >= v[i]; j -- )
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << f[m] << endl;
return 0;
}