完全背包
每件物品有无限多个
朴素算法
f[i][j]=max(f[i][j],f[i−1][j−k∗v[i]]+k∗w[i])与01背包类似
for (int i = 1;i <= n;++i) { for (int j = 0;j <= m;++j) { for (int k = 0;v[i] * k <= j;++k) { f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]); } } }
优化做法
for (int i = 1;i <= n;++i) { for (int j = 0;j <= m;++j) { f[i][j] = f[i - 1][j]; if(j >= v[i])f[i][j] = max(f[i][j],f[i][j -v[i]] + w[i]); } }
优化成一维
在计算f[j]时 因为j−v[i]小于j所以此时的f[j−v[i]]被更新到了第i 维 与原式相符 所以j不需要从大到小枚举
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]); } }
当优化到一维时，只有完全背包的体积是从小到大循环的
for 物品：
for 体积：
for 决策：
