👉背包问题👈
有 n 个物品和一个大小为 m 的背包，给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值。问最多能装入背包的总价值是多大?
思路
class Solution { public: int backPackII(int m, vector<int> &a, vector<int> &v) { int n = a.size(); // 商品个数 vector<vector<int>> maxValue(n + 1, vector<int>(m + 1, 0)); // 初识状态 for(int i = 1; i <= n; ++i) { for(int j = 1; j <= m; ++j) { if(a[i - 1] <= j) // 第i个物品能放入大小为j的背包，可以放入也可以不放入 { maxValue[i][j] = max(maxValue[i - 1][j], maxValue[i - 1][j - a[i - 1]] + v[i - 1]); } else // 第i个商品不能放入大小为j的背包 { maxValue[i][j] = maxValue[i - 1][j]; } } } return maxValue[n][m]; } };
空间复杂度优化
通过上面的分析，当前行当前列的值取决于上一行当前列的值和上一行某一列的值，所以我们只需要保存上一行的值就行了，而保存上一行的值只需要一维数组就可以保存下来了，就相当于将原来的二维数组压缩成了一维数组。如果不能放入第 i 个物品时，此时的最大价值还不需要改变。还有一个值得注意的问题：更新最大价值需要从后向前更新，因为当前的最大价值是取决于上一次循环得到的最大价值，所以前面的上一次得到的最大价值不能先修改。所以上面的代码，我们可以优化成下面的样子。
class Solution { public: int backPackII(int m, vector<int> &a, vector<int> &v) { int n = a.size(); vector<int> maxValue(m + 1, 0); for(int i = 1; i <= n; ++i) { for(int j = m; j > 0; --j) { // 能放入第i个物品时，可以放入也可以不放入 // 不能放入第i个物品时，不需要修改最大价值 if(a[i - 1] <= j) { maxValue[j] = max(maxValue[j], maxValue[j - a[i - 1]] + v[i - 1]); } } } return maxValue[m]; } };
👉总结👈
那么以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家！💖💝❣️
