网站开发中期检查,dedecms制作网站地图,唐山建设企业网站,如何制作微信图文链接文章目录 #x1f3b5;二维费用背包问题#x1f3b6;引言#x1f3b6;问题定义#x1f3b6;动态规划思想#x1f3b6;状态定义和状态转移方程#x1f3b6;初始条件和边界情况 #x1f3b5;例题#x1f3b6;1.一和零#x1f3b6;2.盈利计划 #x1f3b5;总结 #x1… 文章目录 二维费用背包问题引言问题定义动态规划思想状态定义和状态转移方程初始条件和边界情况 例题1.一和零2.盈利计划 总结 二维费用背包问题
引言
背包问题是算法中的经典问题之一其变种繁多。本文将介绍二维费用背包问题及其解决方案。
问题定义
二维费用背包问题可以描述为给定 (N) 个物品每个物品有两个费用和一个价值在两种费用的限制下如何选择物品使得总价值最大。
动态规划思想
动态规划是解决背包问题的常用方法。通过定义合适的状态和状态转移方程我们可以有效地解决二维费用背包问题。
状态定义和状态转移方程
我们定义 dp[i][j][k] 表示前 i 个物品在费用1不超过 j 和费用2不超过 k 的情况下的最大价值。状态转移方程为 d p [ i ] [ j ] [ k ] max ( d p [ i − 1 ] [ j ] [ k ] , d p [ i − 1 ] [ j − c o s t 1 [ i ] ] [ k − c o s t 2 [ i ] ] v a l u e [ i ] ) dp[i][j][k] \max(dp[i-1][j][k], dp[i-1][j-cost1[i]][k-cost2[i]] value[i]) 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的个数的限制这里的物品其实就是每个字符串。 状态表示 d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k]表示从前 i i i个物品中选择的所有组合中满足0的个数不大于m1的个数不大于n个的所有组合中子集长度最大的那个的长度。 状态转移方程 这里的a和b代表的是当前i位置字符串中0和1分别的个数所以我们在进行填表的时候应该遍历一下字符串将当中的0和1分别记录一下状态转移方程 d p [ i ] [ j ] [ k ] m a x ( d p [ i − 1 ] [ j ] [ k ] , d p [ i − 1 ] [ j − a ] [ k − b ] ) dp[i][j][k]max(dp[i-1][j][k],dp[i-1][j-a][k-b]) dp[i][j][k]max(dp[i−1][j][k],dp[i−1][j−a][k−b])
初始化
代码 未优化的代码
class Solution {
public:int findMaxForm(vectorstring strs, int m, int n){int sz strs.size();vectorvectorvectorint dp(sz 1, vectorvectorint(m 1, vectorint(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(vectorstring strs, int m, int n){int sz strs.size();vectorvectorint dp(m 1, vectorint(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下标是对应的。 根据上面的图片加上题目要求我们可以得知我们每次选择的利润必须大于给定的 m i n P r o f i t minProfit minProfit然后每次需要的人口不能超过 n n n最后求出满足这个条件的所有组合有多少种。 状态表示 d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k]表示从前i个工作计划中选择人数不超过i的但是盈利大于k的所有组合数的总和。 状态转移方程 第一种状态不选择i位置 d p [ i − 1 ] [ j ] [ k ] dp[i-1][j][k] dp[i−1][j][k]
第二种状态选择i位置首先考虑二维 d p [ i − 1 ] [ j − g r o u p [ i ] ] dp[i-1][j-group[i]] dp[i−1][j−group[i]]这里我们考虑一下 j − g r o u p [ i ] ≤ 0 j-group[i]\leq0 j−group[i]≤0是否成立将group[i]移到右边去可以得到 j ≤ g r o u p [ i ] j\leq group[i] j≤group[i]这个是什么意思呢表示i工作需要的人口是大于总人口j的所以这肯定是不可能的所以这里中只能是 j − g r o u p [ i ] ≥ 0 j-group[i]\geq0 j−group[i]≥0我们再来考虑三维的 d p [ i − 1 ] [ j − g r o u p [ i ] ] [ k − p r o f i t [ i ] ] dp[i-1][j-group[i]][k-profit[i]] dp[i−1][j−group[i]][k−profit[i]]我们来考虑 k − p r o f i t [ i ] ≤ 0 k-profit[i]\leq0 k−profit[i]≤0是否成立首先我们还是继续移一下项 k ≤ p r o f i t [ i ] k \leq profit[i] k≤profit[i]这里k表示总的利润profit表示当前工作产出的利润所以这里的意思就表示无论前面总利润是多少这里都都能满足当前的利润所以我们只需要选择0即可所以第二种状态 d p [ i − 1 ] [ j − g r o u p [ i ] ] [ m a x ( 0 , k − p r o f i t [ i ] ) ] dp[i-1][j-group[i]][max(0,k-profit[i])] dp[i−1][j−group[i]][max(0,k−profit[i])]
最后这两种状态的总和就是当前状态的所有组合的总和 d p [ i ] [ j ] [ k ] d p [ i − 1 ] [ j ] [ k ] d p [ i − 1 ] [ j − g r o u p [ i ] ] [ m a x ( 0 , k − p r o f i t [ i ] ) ] dp[i][j][k]dp[i-1][j][k]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, vectorint group, vectorint profit) {int len group.size();int MOD 1e9 7;vectorvectorvectorint dp(len 1, vectorvectorint(n 1, vectorint(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, vectorint group, vectorint profit)
{int len group.size();int MOD 1e9 7;vectorvectorint dp(n 1, vectorint(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];
}运行结果
总结
通过本文的学习我们了解了二维费用背包问题的基本概念和解决方法。与传统的单一费用背包问题不同二维费用背包问题在解决时需要同时考虑两种费用的限制这使得问题更具挑战性但也更贴近实际应用场景。我们通过动态规划的方法逐步构建状态转移方程并利用二维数组来存储中间结果从而实现了对问题的高效求解。
在实际应用中掌握二维费用背包问题的解决思路可以帮助我们在资源分配、投资组合等多方面优化决策。希望通过本次的学习大家不仅能够掌握相关的算法技巧还能够举一反三灵活应用于更多复杂的优化问题中。
今后我们将继续探讨更为复杂的动态规划问题进一步提升算法设计和问题求解能力。谢谢大家的阅读希望本文对你有所帮助。
