【动态规划】须知少时凌云志，曾许人间第一流 - 二维01背包问题

本篇博客给大家带来的是二维01背包问题之动态规划解法技巧.
🐎文章专栏: 动态规划
🚀若有问题 评论区见
❤ 欢迎大家点赞 评论 收藏 分享
如果你不知道分享给谁,那就分享给薯条.
你们的支持是我不断创作的动力 .

王子,公主请阅🚀

• 要开心
• • 要快乐
  • • 顺便进步
• 1. 一和零
• 2. 盈利计划

要开心

要快乐

顺便进步

1. 一和零

题目链接: 474. 一和零

题目内容:
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：

输入：strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {“10”,“0001”,“1”,“0”} ，因此答案是 4 。
其他满足题意但较小的子集包括 {“0001”,“1”} 和 {“10”,“1”,“0”} 。{“111001”} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
示例 2：

输入：strs = [“10”, “0”, “1”], m = 1, n = 1
输出：2
解释：最大的子集是 {“0”, “1”} ，所以答案是 2 。

第一步 分析

在前面学习01背包问题和完全背包问题的时候, 我们遇到的限制条件只有一个, 这道题中出现了两个:
最多 有 m 个 0 和 n 个 1
只有一个限定条件的01背包问题的状态表示是这样定义的: dp[i][j]表示 从前 i 个物品中选, 总体积不超过 j ,所有选法的最大价值.
类比过来本题的状态表示可以这么定义:
dp[i][j][k]表示从前 i 个字符串中挑选, 字符0个数不超过 j , 字符1 的个数不超过 k,所有选法中的最大长度.

第二步 动态规划

1. 状态表示
dp[i][j][k]表示从前 i 个字符串中挑选, 字符0个数不超过 j , 字符1 的个数不超过 k,所有选法中的最大长度.

2. 状态转移方程

以某 i 位置是否选择来划分情况:
如果选了strs[i]的话, j需要减去strs[i]含有的0个数,k需要减去strs[j]含有的1个数. 这里假设strs[i]有a个0,b个1;
不选strs[i]: dp[i][j][k] = dp[i-1][j][k];①
选了strs[i]: dp[i][j][k] = dp[i-1][j-a][k-b];②
结合①②又 题目所求的是最大子集长度,所以:
dp[i][j][k] = Math.max(dp[i-1][j][k],dp[i-1][j-a][k-b]+1);
②式应用的前提是: j >= a && k >= b

3. 初始化

多创建了一行一列一竖,处理两个细节:
1. dp表与原数组下标之间的对应关系:
因为状态转移方程中并没有涉及到原数组strs的式子,所以可以不用管这一步.
2. 初始化虚拟节点:
因为有j >= a && k >= b的限制(在一维的题中有解释过,具体可以看我之前的文章),所以只需初始化i = 0的节点即可, i=0 的时候没有字符串课选,最大长度为0,所以dp[0][j][k] = 0;

4. 填表顺序
看状态转移方程,
要想填dp[i][j][k] 就得直到dp[i-1][j][k] 和 dp[i-1][j-a][k-b], 所以需要保证 i 按小到大的顺序去填写.

5. 返回值
根据状态表示并结合题目要求,返回dp[strs.length()][m][n]即可.

6. 代码优化
跟01背包问题的优化方式一毛一样,
删掉第一维[i],然后 两层for循环的填表顺序改为从大到小.
详细看01背包问题, 文章链接: 01背包问题

第三步 代码实现

class Solution { public int findMaxForm(String[] strs, int m, int n) { //优化前: // int len = strs.length; // int[][][] dp = new int[len+1][m+1][n+1]; // for(int i = 1;i <= len;++i) { // //统计各个字符串的个数 // int a = 0;//记录0的个数 // int b = 0;//记录1的个数 // for(char ch : strs[i-1].toCharArray()) { // 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] = Math.max(dp[i][j][k],dp[i-1][j-a][k-b]+1); // } // } // } // } // return dp[len][m][n]; //优化后: int len = strs.length; int[][] dp = new int[m+1][n+1]; for(int i = 1;i <= len;++i) { //统计各个字符串的个数 int a = 0;//记录0的个数 int b = 0;//记录1的个数 for(char ch : strs[i-1].toCharArray()) { if(ch == \'0\') {  a++; }else {  b++; } } for(int j = m;j >= a;--j) { for(int k = n;k >= b;--k) {  dp[j][k] = Math.max(dp[j][k],dp[j-a][k-b]+1); } } } return dp[m][n]; }}

2. 盈利计划

题目链接: 879. 盈利计划

题目内容:
集团里有 n 名员工，他们可以完成各种各样的工作创造利润。

第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。

工作的任何至少产生 minProfit 利润的子集称为 盈利计划 。并且工作的成员总数最多为 n 。

有多少种计划可以选择？因为答案很大，所以 返回结果模 10^9 + 7 的值。

示例 1：

输入：n = 5, minProfit = 3, group = [2,2], profit = [2,3]
输出：2
解释：至少产生 3 的利润，该集团可以完成工作 0 和工作 1 ，或仅完成工作 1 。
总的来说，有两种计划。
示例 2：

输入：n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
输出：7
解释：至少产生 5 的利润，只要完成其中一种工作就行，所以该集团可以完成任何工作。
有 7 种可能的计划：(0)，(1)，(2)，(0,1)，(0,2)，(1,2)，以及 (0,1,2) 。

第一步 动态规划

1. 状态表示
dp[i][j][k]表示在前 i 个工作中选,参与成员总数不超过 j,产生的利润至少为k,总共有多少种选法.

2. 状态转移方程

根据 i 位置的 选择与否来划分情况:
profit[i]不选, dp[i][j][k] = dp[i-1][ j][k];①
profit[i]选, dp[i][j][k] = dp[i-1][ j-group[i]][k-profit[i]].Ⅱ
考虑到profit[i] 有可能大于 k,而数组的下标不能为负数. 所以Ⅱ式不能这么写.那要怎么办呢?
如果profit[i] > k, 但是profit[i]利润就满足了条件 那么前i-1个位置的利润可以为0.
所以, dp[i][j][k] = dp[i-1][ j-group[i]][Math.max(0,(k-profit[i]))];②
根据①②并结合题目要求
dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-group[i]][Math.max(0,(k-profit[i]))];
使用②式的前提是: j >= group[i] && k <= profit[i];

3. 初始化

多创建了一行一列一竖,处理两个细节:
1. dp表与原数组下标之间的对应关系:
i – i-1;
2. 初始化虚拟节点.
j 和 k都是有限制的,j = 0和k = 0在填表中填即可, 主要初始化 i=0时的情况.
当i=0 && k =0时,
无论 j 是多少dp[0][j][0] = 1;
即当没有工作的时候,利润至少为0,人数不超过 j.有几种选法, 只有一种,就是不选.

4. 填表顺序
与上一道题一样, i从小到大填写.

5. 返回值
根据状态表示并结合题目要求: return dp[profit.length][n][minprofit];

6. 优化
1. 删除第一维[i]
2. 两层for循环的填表顺序改为从大到小

第二步 代码实现

class Solution { public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) { //优化前: // int m = profit.length; // int[][][] dp = new int[m+1][n+1][minProfit+1]; // //2. 初始化 // for(int i = 0;i <= n;i++) { // dp[0][i][0] = 1; // } // for(int i = 1;i <= m;++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] %= 1e9+7; // } // } // } // } // return dp[m][n][minProfit]; //优化后: int m = profit.length; int[][] dp = new int[n+1][minProfit+1]; //2. 初始化 for(int i = 0;i <= n;i++) { dp[i][0] = 1; } for(int i = 1;i <= m;++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] %= 1e9+7; } } } return dp[n][minProfit]; }}

本篇博客到这里就结束啦, 感谢观看 ❤❤❤

🐎期待与你的下一次相遇😊😊😊

免费商用字体下载