题面：
有 \(N\) 件物品和一个容量是 \(V\) 的背包。每件物品只能使用一次。
第 \(i\) 件物品的体积是 \(v_i\)，价值是 \(w_i\)。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
- 有限集的最优问题：乘法原理，总方案数为 \(2^n\) ，在所有的方案中选择一个价值最大的方案。
- 对于 \(F(i,j)\)：
- 集合：只考虑前 \(i\) 个物品，且总体积不超过 \(j\) ；
- 属性：题目要求我们求最大价值，则其属性就是 \(max\)。
- 划分方案：所有不选第 \(i\) 个物品的方案 / 所有选第 \(i\) 个物品的方案（不重不漏）
- 左集合（不选）：由于它在 \(F(i, j)\) 内，且不包含 \(i\)，即相当于 \(F(i-1, j)\)；
- 即问题转化为：考虑前 \(i-1\) 个物品且总体积不超过 \(j\) 的情况下的最优解。
- 将原始问题转化为一个更小的子问题进行求解，从而实现问题的分解和状态转移
- 右集合（选）：再次细分，将 \(i\) 单独拿出来，得到 \(F(i-1, j-Vi)\)；
- 表示考虑前 \(i-1\) 个物品且总体积不超过 \(j-Vi\) 的集合。
- 也就是说求右边的最大值：\(max(F(i-1, j-Vi) + Wi)\)；
- 即先前右集合的基础上加上第 \(i\) 个物品的价值 \(Wi\)。
- 右集合不一定存在（\(j＜Vi\)），故特判：\(j ≥ Vi ≥ 0\)；
- 状态转移方程：\(F(i, j) = max(F(i-1, j), F(i-1, j-Vi) + Wi)\) \(j≥Vi\)；
- 左集合（不选）：由于它在 \(F(i, j)\) 内，且不包含 \(i\)，即相当于 \(F(i-1, j)\)；
- 时间复杂度：物品数量 × 背包容量，因此本题的时间复杂度是 \(O(nv)\)。
- 循环顺序问题：板子为外层循环遍历物品，内层循环遍历容量；
- 二维数组的两个
for遍历的先后循序可以颠倒; - 一维数组的两个
for循环先后循序一定是先遍历物品，再遍历背包容量。
- 二维数组的两个
- 滚动数组的容量倒序遍历问题[1]：每次取的状态不会和之前取的状态重合；
- 对于二维dp，
dp[i][j]都是通过上一层即dp[i - 1][j]计算而来，本层的dp[i][j]并不会被覆盖。
- 对于二维dp，
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, m;
int v[N], w[N];
int f[N][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 = 1; j <= m; j++) {
f[i][j] = f[i - 1][j];
if (j >= v[i])
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
}
cout << f[n][m];
//优化-使用滚动数组：状态转移方程中的 F(i, j) 只与 F(i-1, x) 有关，且 x ≤ j
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]);
//从大到小枚举背包容量 j：确保在计算 f[j] 时，f[j-v[i]] 已经被更新过：
//后面的数据依赖于左上方的数据（f(i-1,j-x)），从小到大循环会导致状态依赖在计算前就被覆盖，即f(i-1,j-x)会在f(i,j)之前被更新为f(i,j-x)
cout << f[m] << endl;
return 0;
}