🎵二维费用背包问题

🎶引言

背包问题是算法中的经典问题之一，其变种繁多。本文将介绍二维费用背包问题及其解决方案。

🎶问题定义

二维费用背包问题可以描述为：给定 (N) 个物品，每个物品有两个费用和一个价值，在两种费用的限制下，如何选择物品使得总价值最大。

🎶动态规划思想

动态规划是解决背包问题的常用方法。通过定义合适的状态和状态转移方程，我们可以有效地解决二维费用背包问题。

🎶状态定义和状态转移方程

我们定义 dp[i][j][k] 表示前 i 个物品在费用1不超过 j 和费用2不超过 k 的情况下的最大价值。状态转移方程为：

$dp[i][j][k]=\max (dp[i-1][j][k],dp[i-1][j-cost1[i]][k-cost2[i]]+value[i])$

🎶初始条件和边界情况

初始条件为 dp[0][j][k] = 0，表示没有物品时的最大价值为 0。边界条件需要根据实际问题进行处理。

🎵例题

🎶1.一和零

题目：

样例输出和输入：

算法原理：
这道题就是让我们找子集的长度，这个子集满足：当中的0不大于m个，当中的1不大于n个，最后返回最大的子集的长度，所以我们首先想到的是二维费用背包问题，因为有两个限制，这里的背包的限制就是0和1的个数的限制，这里的物品其实就是每个字符串。
状态表示：$dp[i][j][k]$表示从前$i$个物品中选择的所有组合中，满足0的个数不大于m，1的个数不大于n个的所有组合中子集长度最大的那个的长度。
状态转移方程：

这里的a和b代表的是当前i位置字符串中0和1分别的个数，所以我们在进行填表的时候应该遍历一下字符串，将当中的0和1分别记录一下，状态转移方程：

$dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-a][k-b])$

初始化：

代码：
未优化的代码：

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n)
    {
        int sz = strs.size();
        vector<vector<vector<int>>> dp(sz + 1, vector<vector<int>>(m + 1, vector<int>(n + 1)));
        for (int i = 1;i <= sz;i++)
        {
            //统计一下字符串中0和1的个数
            int a = 0, b = 0;
            for (auto e : strs[i - 1])
            {
                if (e == '1')b++;
                else a++;
            }
            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 - 1][j][k], dp[i - 1][j - a][k - b] + 1);
                }
            }
        }
        return dp[sz][m][n];
    }
};

滚动数组优化的代码：

class Solution {
public:
	int findMaxForm(vector<string>& strs, int m, int n)
	{
		int sz = strs.size();
		vector<vector<int>> dp(m + 1, vector<int>(n + 1));
		for (int i = 1;i <= sz;i++)
		{
			//统计一下字符串中0和1的个数
			int a = 0, b = 0;
			for (auto e : strs[i - 1])
			{
				if (e == '1')b++;
				else a++;
			}
			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.盈利计划

题目：

样例输出和输入：

算法原理：
这道题每个group对应一个profit，下标是对应的。

根据上面的图片加上题目要求，我们可以得知，我们每次选择的利润必须大于给定的$minProfit$然后每次需要的人口不能超过$n$，最后求出满足这个条件的所有组合有多少种。
状态表示：$dp[i][j][k]$表示从前i个工作计划中选择，人数不超过i的，但是盈利大于k的所有组合数的总和。
状态转移方程：
第一种状态：不选择i位置，$dp[i-1][j][k]$

第二种状态：选择i位置，首先考虑二维$dp[i-1][j-group[i]]$这里我们考虑一下$j-group[i]\le 0$是否成立将group[i]移到右边去可以得到：$j\le group[i]$这个是什么意思呢？表示i工作需要的人口是大于总人口j的，所以这肯定是不可能的，所以这里中只能是$j-group[i]\ge 0$，我们再来考虑三维的：$dp[i-1][j-group[i]][k-profit[i]]$我们来考虑$k-profit[i]\le 0$是否成立，首先我们还是继续移一下项：$k\le profit[i]$这里k表示总的利润，profit表示当前工作产出的利润，所以这里的意思就表示无论前面总利润是多少，这里都都能满足当前的利润，所以我们只需要选择0即可，所以第二种状态：

$dp[i-1][j-group[i]][max(0,k-profit[i])]$

最后这两种状态的总和就是当前状态的所有组合的总和：

$dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-group[i]][max(0,k-profit[i])]$

代码：
未优化的代码：

class Solution {
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) 
    {
        int len = group.size();
        int MOD = 1e9 + 7;
        vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(n + 1, vector<int>(minProfit + 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 <= minProfit;k++)
                {
                    dp[i][j][k] = dp[i - 1][j][k];
                    if (j >= group[i-1])
                        dp[i][j][k] += dp[i - 1][j - group[i - 1]][max(0, k - profit[i - 1])];
                    dp[i][j][k] %= MOD;
                }
            }
        }
        return dp[len][n][minProfit];
    }
};

优化过后的代码：

int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) 
{
	int len = group.size();
	int MOD = 1e9 + 7;
	vector<vector<int>> dp(n + 1, vector<int>(minProfit + 1));
	for (int j = 0;j <= n;j++)dp[j][0] = 1;
	for (int i = 1;i <= len;i++)
		for (int j = n;j >= group[i - 1];j--)
			for (int k = 0;k <= minProfit;k++)
			{
				dp[j][k] += dp[j - group[i - 1]][max(0, k - profit[i - 1])];
				dp[j][k] %= MOD;
			}
	return dp[n][minProfit];
}

运行结果：

🎵总结

通过本文的学习，我们了解了二维费用背包问题的基本概念和解决方法。与传统的单一费用背包问题不同，二维费用背包问题在解决时需要同时考虑两种费用的限制，这使得问题更具挑战性，但也更贴近实际应用场景。我们通过动态规划的方法，逐步构建状态转移方程，并利用二维数组来存储中间结果，从而实现了对问题的高效求解。

在实际应用中，掌握二维费用背包问题的解决思路，可以帮助我们在资源分配、投资组合等多方面优化决策。希望通过本次的学习，大家不仅能够掌握相关的算法技巧，还能够举一反三，灵活应用于更多复杂的优化问题中。

今后，我们将继续探讨更为复杂的动态规划问题，进一步提升算法设计和问题求解能力。谢谢大家的阅读，希望本文对你有所帮助。