01背包

解题

• 这道题无法用贪心求解。例如样例2，如果用贪心思路，应该先装第 1 件物品，这样就无法装其它物品了，只能得到 15 的价值。贪心题在这里
• 约定用f[i][j]表示将前 i 件物品 -> 容量为 j 的背包能够获得的最大总价值
• 如果 j < w[i]，则装不下第 i 件物品，这时候相当于将前 i - 1 件物品 -> 容量为 j 的背包，
  f[i][j] = f[i - 1][j]
• 如果 j >= w[i]，能装得下第 i 件物品。如果选择装第 i 件物品，它的价值为 v[i] ，背包剩余容量为 j - w[i] ，那么将前 i - 1 件物品 -> 容量为 j - w[i] 的背包，获得的最大价值为f[i - 1][j - w[i]] + v[i]，比较装与不装的最优结果是：
  f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i])
• 将 n 件物品 -> 容量为 m 的背包，能够获得的最大总价值就是f[n][m]

这是完整代码

#include using namespace std;int m, n;int w[39], v[39];int f[39][209];int main() {cin >> m >> n;for (int i = 1; i <= n; i ++) {cin >> w[i] >> v[i];}for (int i = 1; i <= n; i ++) {for (int j = 1; j <= m; j ++) {if (j < w[i]) {f[i][j] = f[i - 1][j];}else {f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);}}}cout << f[n][m];return 0;}

优化

• 和前一篇文章的优化思路一样，我们来看下面这条核心语句，看看如何将其中的二维数组 f 压缩成一维数组
  f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i])
• 将二维数组 f 看成 n 行 m 列的矩阵，循环变量 i 是从小到大，第 i 行的元素可以通过已经计算好的第 i - 1 行的元素递推
• 赋值语句右边的f[i - 1][j - w[i]]这一项，在第 j 列的左侧，因此压缩成一维数组时，循环变量 j 必须从大到小循环，才能避免更新后的元素对接下来赋值语句的影响
• 另外一条语句f[i][j] = f[i - 1][j]，当压缩成一维数组时，变成f[j] = f[j]，可以省略
• 将 n 件物品 -> 容量为 m 的背包，能够获得的最大总价值就是f[m]

优化后的代码，空间复杂度为o(n)

#include using namespace std;int m, n;int w[39], v[39];int f[209];int main() {cin >> m >> n;for (int i = 1; i <= n; i ++) {cin >> w[i] >> v[i];}for (int i = 1; i <= n; i ++) {for (int j = m; j >= w[i]; j --) {f[j] = max(f[j], f[j - w[i]] + v[i]);}}cout << f[m];return 0;}

集装箱装载

除了上面一题的思路之外，这道题还有另外一种思路

解题

• 如果能够用前 i 件物品凑出重量 j，则将f[j]设为true；如果不能，则将f[j]设为false。
• 如果因为选择了第 i 件物品才凑出重量 j，那么前 i - 1 件物品一定可以凑出重量 j - w[i]，因此:
  f[j] = f[j] | f[j - w[i]]
• 初始化时，需要将f[1] ~ f[m]设为false，因为还没有凑出这些重量；而f[0]应该设为true，因为在没有选择任何物品时，重量为 0
• 最后要找到将 n 件物品 -> 容量为 m 的背包能够获得的最大重量，应该从 m 到 1 枚举 j，如果f[j] == true，说明可以获得重量 j，不用再继续枚举了，程序结束

这是完整代码

#include using namespace std;int n, m;int w[10009];bool f[40000];int main() {cin >> n >> m;for (int i = 1; i <= n; i ++) cin >> w[i];f[0] = true;for (int i = 1; i <= n; i ++) {for (int j = m; j >= w[i]; j --) {f[j] |= f[j - w[i]];}}for (int j = m; j >= 1; j --) {if (f[j] == true) {cout << j;return 0;}}return 0;}

换一个角度

• 如果在装第 i 件物品前，f[j] == true，那么装了第 i 件物品可以得到 j + w[i] 的重量
• 这样递推有个前提，装第 i 件物品之前的重量不能超过 m - w[i]，否则就超过了背包的容量

记住这个思路，在后面的题目中会用到这个方法

#include using namespace std;int n, m;int w[10009];bool f[40000];int main() {cin >> n >> m;for (int i = 1; i <= n; i ++) cin >> w[i];f[0] = true;for (int i = 1; i <= n; i ++) {for (int j = m - w[i]; j >= 0; j --) {if (f[j]) {f[j + w[i]] = true;}}}for (int j = m; j >= 1; j --) {if (f[j] == true) {cout << j;return 0;}}return 0;}

相关习题

• 开心的金明
• 奖品
• 砝码称重
• 积木城堡
• 阶乘的和