完全背包问题
完全背包问题就是指已知一个体积为m的背包，共有n种物品，其中每种物品有其特定的体积v[i], 和权重w[i]，每种物品有无限个，要求从中选取物品装进背包，使总权值最大。
首先是总体需要弄清楚的模板发：
状态计算如下：（按照选择第 i 件物品的数量来划分）
f [i, j] = max( f [ i - 1, j ], f [ i , j - v ] + w, f [ i, j - 2 * v ] + 2 * w, f [ i , j - 3 * v ] + 3 * w ......)
于是，我们可以有最原始的代码：
#include using namespace std; const int N = 1010; int n, m; int v[N], w[N]; int f[N][N]; int main() { cin >> n >> m; for (int i = 1; i > v[i] >> w[i] ; for (int i = 1; i <= n; i++) for (int j = 0; j <= m; j++) for (int k = 0; k * v[i] <= j; k++) f[i][j] = max(f[i][j], f[i-1][j - k * v[i]] + k * w[i]); //注意：这里的max里的第二项为 i-1 表示从前 i-1 种里面选择 cout << f[n][m] << endl; return 0; }然而这个代码虽然能够算出结果，但是时间复杂度却不容乐观，于是我们可以简化一下代码，减少一层循环。
我们先列出f [ i, j ] 和 f [ i , j - v ]（其中v表示第 i 件物品的体积）如下：
f [ i , j ] = max ( f [ i - 1, j ], f [ i - 1 , j - v ] + w , f [ i - 1, j - 2v ] + 2w , f [ i - 1, j - 3v ] + 3w, ......)
f [ i , j - v ] = max ( f [ i - 1, j - v ] , f [ i - 1 , j - 2v ] + w, f [ i - 1, j - 3v ] + 2w, ......)
于是我们可以惊奇地发现 f [ i , j ] = max ( f [ i - 1, j ] , f [ i , j - v ] + w ), 于是之前的代码可以做一下简化：
#include const int N = 1010; using namespace std; int n, m; int v[N], w[N]; int f[N][N]; int main() { cin >> n >> m; for (int i = 1; i > v[i] >> w[i]; for (int i = 1; i <= n; i++) for (int j = 0; j = v[i]) f[i][j] = max(f[i-1][j], f[i][j - v[i]] + w[i]); //注意前一个为 i - 1，后一个为i } cout << f[n][m] << endl; return 0; }最后，这个状态方程可以转化成一维滚动数组， 也就是完全背包的终极表达形式：
#include const int N = 1010; using namespace std; int n, m; int v[N], w[N]; int f[N]; int main() { cin >> n >> m; for (int i = 1; i > 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]); //注意：由于原来二元形式下两个状态表达都是f[i]XX 所以不存在01背包背景下的覆盖问题，所以j可以从v[i]开始正序遍历 } cout << f[m] << endl; return 0; }
作者：Victayria
