绿色配色的企业网站,如何改进网站服务建设和管理,深圳高端画册设计,大型企业网络搭建目录 二维费用的背包问题详解
总结#xff1a;
空间优化#xff1a;
1. 状态定义
2. 状态转移方程
3. 初始化
4. 遍历顺序
5. 时间复杂度
例题
1#xff0c;一和零
2#xff0c;盈利计划 二维费用的背包问题详解
前面讲到的01背包中#xff0c;对物品的限定条件…目录 二维费用的背包问题详解
总结
空间优化
1. 状态定义
2. 状态转移方程
3. 初始化
4. 遍历顺序
5. 时间复杂度
例题
1一和零
2盈利计划 二维费用的背包问题详解
前面讲到的01背包中对物品的限定条件只有一个体积而在二维费用的背包问题中相当于增加了一个限定条件比如
【问题描述】 输入 物品数量 N每个物品有重量 wi、体积 vi 和价值 vali。 背包最大承重 W最大体积 V。 目标选择物品装入背包使得总重量 ≤ W总体积 ≤ V且总价值最大。
加了一个限定条件重量那么状态表示也需加上一维。二维费用的背包问题时01背包问题的一个延申状态表示和状态转移方程的分析与01背包类似。
状态表示是dp[i][j][k]表示前i个物品在重量限制j和体积限制k下的最大价值。
状态转移方程就是dp[i][j][k] max([i-1]dp[j][k], dp[i][j - w[i]][k - v[i]] val[i]),推理过程与01背包类似。 总结
常规的0-1背包问题可以用动态规划来解决状态通常是dp[i][j]表示前i个物品在容量j下的最大价值。对于二维费用的情况可能需要扩展状态到两个维度。比如状态可能是dp[i][j][k]表示前i个物品在重量限制j和体积限制k下的最大价值。但这样的话状态空间会变得很大尤其是当j和k都较大的时候时间和空间复杂度可能很高。不过可能可以通过优化来减少空间的使用比如使用滚动数组。
空间优化
在常规的0-1背包问题中我们可以将二维的dp优化为一维数组通过逆序遍历容量来避免覆盖之前的状态。那么在二维费用的情况下使用二维的dp数组而不是三维的。例如状态dp[j][k]表示在重量j和体积k的限制下能获得的最大价值。这样的话每次处理一个物品时需要从后往前更新这两个维度以避免重复选择同一物品。这可能需要双重循环遍历重量和体积的容量。
1. 状态定义 定义二维数组 dp[j][k]表示背包在承重 j 和体积 k 的限制下能获得的最大价值。 最终目标求解 dp[W][V]。
2. 状态转移方程
对每个物品i逆序更新所有可能的重量和体积组合
dp[j][k]max(dp[j][k], dp[j−wi][k−vi]vali)
条件j≥wi 且 k≥vi
3. 初始化 dp[0][0]0空背包价值为0。 其他位置初始化为0表示未装入任何物品时的初始状态。
4. 遍历顺序 外层循环遍历每个物品 i。 内层双循环 重量 j 从 W 逆序递减至 wi。 体积 k 从 V 逆序递减至 vi。 确保每个物品仅被选择一次。 5. 时间复杂度 O(N×W×V)适用于 W 和 VV均较小的情况如 W,V≤10^3。
例题
1一和零
本题链接474. 一和零 - 力扣LeetCode 思路
从strs数组中选取子集有两个限定条件m和n。相当于从背包中选取元素有两个限定条件。 class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {int lenstrs.size();vectorvectorvectorint dp(len1,vectorvectorint(m1,vectorint(n1)));for(int i1;ilen;i){int a0,b0;for(auto ch:strs[i-1])if(ch0) a;else b;for(int j0;jm;j)for(int k0;kn;k){dp[i][j][k]dp[i-1][j][k];if(jakb)dp[i][j][k]max(dp[i][j][k],dp[i-1][j-a][k-b]1);}}return dp[len][m][n];}
}; 空间优化后的代码
class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {int lenstrs.size();vectorvectorint dp(m1,vectorint(n1));for(int i1;ilen;i){int a0,b0;for(auto ch:strs[i-1])if(ch0) a;else b;for(int jm;ja;j--)for(int kn;kb;k--)dp[j][k]max(dp[j][k],dp[j-a][k-b]1);}return dp[m][n];}
};
2盈利计划
本题链接879. 盈利计划 - 力扣LeetCode 思路 class Solution {
public:int profitableSchemes(int n, int m, vectorint g, vectorint p) {int leng.size();const int MOD1e97;vectorvectorvectorint dp(len1,vectorvectorint(n1,vectorint(m1)));for(int j0;jn;j)dp[0][j][0]1;for(int i1;ilen;i)for(int j0;jn;j)for(int k0;km;k){dp[i][j][k]dp[i-1][j][k];if(jg[i-1])dp[i][j][k]dp[i-1][j-g[i-1]][max(0,k-p[i-1])];dp[i][j][k]%MOD;}return dp[len][n][m];}
}; 空间优化后的代码
class Solution {
public:int profitableSchemes(int n, int m, vectorint g, vectorint p) {int leng.size();const int MOD1e97;vectorvectorint dp(n1,vectorint(m1));for(int j0;jn;j)dp[j][0]1;for(int i1;ilen;i)for(int jn;jg[i-1];j--)for(int km;k0;k--){dp[j][k]dp[j-g[i-1]][max(0,k-p[i-1])];dp[j][k]%MOD;}return dp[n][m];}
};
