AcWing
3. 完全背包问题
完全背包问题。定义二维状态数组f[i][j]表示考虑前i种物品，背包容量为j时，所有方案中的最大价值。
可以将f[i][j]分为以下若干个集合：
- 背包容量为
j时，装0个物品i； - 背包容量为
j时，装1个物品i； - ……
- 背包容量为
j时，装k个物品i； - ……
保证将f[i][j]分为这些集合之后不重不漏。则对于普遍的f[i][j]，有:
f[i][j] = max{f[i-1][j], f[i-1][j-v[i]]+w[i], f[i-1][j-2v[i]]+2w[i], ...}
同时注意到：
f[i][j-v[i]] = max{f[i-1][j-v[i]] + f[i-1][j-2v[i]]+w[i] + ...} = max{f[i-1][j-v[i]]+w[i], f[i-1][j-2v[i]]+2w[i], ...} - w[i]
所以：
max{f[i-1][j-v[i]]+w[i], f[i-1][j-2v[i]]+2w[i], ...} = f[i][j-v[i]]+w[i]
f[i][j] = max{f[i-1][j], f[i][j-v[i]]+w[i]}
-
当
j >= v[i]时，f[i][j] = max{f[i-1][j], f[i][j-v[i]]+w[i]}； -
当
j < v[i]时，f[i][j] = f[i-1][j].
考虑边界条件，f[0][0] = 0, f[0][1] = 0, f[0][2] = 0, ...，即当不取任何一个物品时，总价值一定为0.
考虑优化空间，使用一维数组，外层循环依次枚举物品种类，内层循环必须从小到大枚举背包容量，这样f[j]取得的是上一种物品时的值，f[j-v[i]]取得的是本种物品时的值。
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 1010, M = 1010;
int v[N], w[N];
int f[M];
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;
}