01背包
每件物品只有一个
状态表示：f[i][j] 表示所有只从前 i 个物品中选 且总体积不超过 j 的选法的价值最大值
朴素算法
分为两种情况：①不选第i个物品f[i−1][j]
②选第i个物品 状态方程可以由f[i−1][j−v]+w得到f[i−1][j−v]+w表示前i−1个物品取总体积不超过j−v的最大价值加上第i 个物品的价值(v , 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 - 1][j - v[i]] + w[i]); } } cout << f[n][m] << endl;
优化成一维
因为对第i维的判断只用到了i−1维，所以可以用滚动数组的思想 由朴素的算法可知i ii维都是由i−1维转移过来的 如果对j从小到大枚举 计算到f[j]时 此时的f[j−v[i]]小于f[j]已经被更新到第i 维 所以要对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]); } }
