算法系列--动态规划--背包问题(5)--二维费用背包问题（上）
https://developer.aliyun.com/article/1480864?spm=a2c6h.13148508.setting.14.5f4e4f0e82l87T
💕"要平安无事地活下去."💕
作者：Lvzi
文章主要内容：算法系列–动态规划–背包问题(5)–二维费用背包问题
大家好,今天为大家带来的是
算法系列--动态规划--背包问题(5)--二维费用背包问题
二.盈利计划
链接:
https://leetcode.cn/problems/profitable-schemes/description/
分析:
本题有两个限制条件:
- 总人数不能超过n
- 总价格必须 >= minProfit
同样的也是一个二维费用的背包问题,分析思路同上,需要注意的是这里要求的是一共有多少种情况数,所以注意不选也是一种情况
状态表示:
dp[i][j][k]:在前i个物品中选择,总人数不超过j,总利润至少为k,一共有多少种选法
状态转移方程:
注意这里的总利润是至少为k,不是最多,k-p[i]可以小于0,如果小于0,就代表p[i]>k,也就是只要完成第i个任务就可以达到最小的利润,之前的所有任务我不选都行,但是在数组中下标不能为负数,所以当k-p[i] < 0时,应该直接当做总利润至少0的情况
代码:
class Solution { public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) { int len = group.length, MOD = (int)1e9 + 7;// MOD是为了防止数据过大造成越界 int[][][] dp = new int[len + 1][n + 1][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]][Math.max(0, k - profit[i - 1])]; dp[i][j][k] %= MOD;// 防止越界 } } } return dp[len][n][minProfit]; } }
空间优化代码:
class Solution { public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) { int len = group.length, MOD = (int)1e9 + 7;// MOD是为了防止数据过大造成越界 int[][] dp = new int[n + 1][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 = minProfit; k >= 0; k--) { dp[j][k] += dp[j - group[i - 1]][Math.max(0, k - profit[i - 1])]; dp[j][k] %= MOD;// 防止越界 } } } return dp[n][minProfit]; } }
总结:
- 二维费用的背包问题其实
多一维的背包问题,区别就在于dp表是一个三维的dp表,但是思路和普通的背包问题类似,遵循相同的状态表示,状态转移方程,填表顺序,以及空间优化 - 二位费用背包问题相较于普通的背包问题
更加灵活,比如第二个题目中不再是不超过xxxx,而是至少实现最低利润
