💕"要平安无事地活下去."💕
作者：Lvzi
文章主要内容：算法系列–动态规划–背包问题(5)–二维费用背包问题
大家好,今天为大家带来的是
算法系列--动态规划--背包问题(5)--二维费用背包问题
一.⼀和零
链接:
https://leetcode.cn/problems/ones-and-zeroes/
分析:
分析题目,题目要求的是满足条件的所有子集中,元素最多的一个,有两个限制条件:
- 子集中
0的个数不能超过m - 子集中
1的个数不能超过n
如果对01背包问题敏感的话,立即就能发现这道题目和01背包问题很像,01背包问题的最大特征就是在所给定的限制条件下,可以实现的最大价值,在01背包问题模版那道题目中,需要满足的限制条件只有一个不超过最大的体积j,但是本题的限制条件有两个(可以理解为多了一个不超过最大重量的限制条件)
这种具有两个限制条件的背包问题我们称之为二维费用的背包问题,包含两种01背包问题和完全背包问题,本题由于可选的物品的数量是唯一的,所以是01背包问题
二位费用的01背包问题其实就是多了一种限制条件,我们只需将dp表设置为三维的即可,分析思路通普通的01背包问题
状态表示:
dp[i][j][k]:在在i个子集中选择,0的数目不超过j,1的数目不超过k,所有的选法中,子集中元素最多的
状态转移方程的分析同样的也是根据最后一个位置的状态去划分
初始化和填表顺序以及返回值和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, b = 0; for(char x : strs[i - 1].toCharArray()) { if(x == '0') a++; else b++; } for(int k = 0; k <= m; k++) { for(int j = 0; j <= n; j++) { dp[i][k][j] = dp[i - 1][k][j]; if(k >= a && j >= b) dp[i][k][j] = Math.max(dp[i][k][j],dp[i - 1][k - a][j - b] + 1); } } } return dp[len][m][n]; } }
同样的,二维费用的背包问题也可以进行空间优化,空间优化的方式和普通的01背包问题一致,分为两步:
- 去掉所有的横坐标
- 更改遍历顺序
空间优化版本:
class Solution { public int findMaxForm(String[] strs, int m, int n) { int len = strs.length; int[][] dp = new int[m + 1][n + 1];// 创建dp表 for(int i = 1; i <= len; i++) { // 求出当前字符中0,1的个数 int a = 0, b = 0; for(char x : strs[i - 1].toCharArray()) { if(x == '0') a++; else b++; } // 填表 for(int k = m; k >= a; k--) { for(int j = n; j >= b; j--) { dp[k][j] = Math.max(dp[k][j],dp[k - a][j - b] + 1); } } } return dp[m][n]; } }
算法系列--动态规划--背包问题(5)--二维费用背包问题（下）https://developer.aliyun.com/article/1480866?spm=a2c6h.13148508.setting.14.352e4f0ecxYhMg
