【背包问题】二维费用的背包问题
目录
二维费用的背包问题详解
总结：
空间优化：
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(vector<string>& strs, int m, int n) {
int len=strs.size();
vector<vector<vector<int>>> dp(len+1,vector<vector<int>>(m+1,vector<int>(n+1)));
for(int i=1;i<=len;i++)
{
int a=0,b=0;
for(auto& ch:strs[i-1])
if(ch=='0') a++;
else b++;
for(int j=0;j<=m;j++)
for(int k=0;k<=n;k++)
{
dp[i][j][k]=dp[i-1][j][k];
if(j>=a&&k>=b)
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(vector<string>& strs, int m, int n) {
int len=strs.size();
vector<vector<int>> dp(m+1,vector<int>(n+1));
for(int i=1;i<=len;i++)
{
int a=0,b=0;
for(auto& ch:strs[i-1])
if(ch=='0') a++;
else b++;
for(int j=m;j>=a;j--)
for(int k=n;k>=b;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, vector<int>& g, vector<int>& p) {
int len=g.size();
const int MOD=1e9+7;
vector<vector<vector<int>>> dp(len+1,vector<vector<int>>(n+1,vector<int>(m+1)));
for(int j=0;j<=n;j++)
dp[0][j][0]=1;
for(int i=1;i<=len;i++)
for(int j=0;j<=n;j++)
for(int k=0;k<=m;k++)
{
dp[i][j][k]=dp[i-1][j][k];
if(j>=g[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, vector<int>& g, vector<int>& p) {
int len=g.size();
const int MOD=1e9+7;
vector<vector<int>> dp(n+1,vector<int>(m+1));
for(int j=0;j<=n;j++)
dp[j][0]=1;
for(int i=1;i<=len;i++)
for(int j=n;j>=g[i-1];j--)
for(int k=m;k>=0;k--)
{
dp[j][k]+=dp[j-g[i-1]][max(0,k-p[i-1])];
dp[j][k]%=MOD;
}
return dp[n][m];
}
};