【动态规划】二维费用的背包问题_二维费用背包

二维费用的背包问题

• 1.一和零
• 2.盈利计划

点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励，我们一起努力吧!😃😃

1.一和零

题目链接： 474. 一和零

题目分析：

找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 ，也就说找到的子集 字符 0 的个数 小于等于 m，字符 1 的个数 小于等于 n。

如果对背包问题敏感，这就是一个背包问题。背包问题问的是给一堆物品，让在这堆物品中选一些物品，在满足某个限定条件下，问一些东西，要么问最大价值，要么问多少种选法。。。。

这道题其实就是背包问题，就是在字符串数组中挑一些字符串出来，需要满足的是两个条件，字符 0 的个数小于等于5，字符 1 的个数小于等于3。像这种满足两个条件的背包问题，我们称之为二维费用背包问题。

二维费用背包问题：之前我们遇到的01背包问题，完全背包问题都只有一个限定条件，二维费用背包就是多了一个限制变成了两个限制条件。

二维费用背包问题也分为二维费用的01背包问题和二维费用的完全背包问题。

这这道题因为每个字符串都面临选or不选两种情况，所以是二维费用的01背包问题。

算法原理：

之前说过所有其余分类的背包问题都是从01背包问题哪里延申出来的。所以我们尝试用01背包问题分析思路来解决我们这里的问题。

1.状态表示

01背包状态表示：

dp[i][j] 表示：从前 i 个物品中挑选，总体积不超过 j，所有选法中，最大的价值

二维费用的01背包问题：其实就只是多加了一个限制条件，之前就只有体积限制，现在不仅有体积还有重量。所以多加一维。

dp[i][j][k] 表示：从前 i 个字符串中挑选，字符 0 的个数不超过 j，字符 1 的个数不超过 k，所有选法中，最长的长度。

2.状态转移方程

本质还是一个01背包问题，所以我们还可以借用之前01背包状态转移方程的思路，根据最后一个位置，划分情况

设最后一个位置的字符串中，字符 0 的个数为 a，字符 1 的个数为 b。

不选 i 位置这个字符串，那就从 0 ~ i - 1 区间内字符串中挑，因为 i 位置都没选，所以0 ~ i - 1 区间内字符串中选 字符 0 的个数不超过 j，字符 1 的个数不超过k，在这两个限制条件下要的最大的长度。就是dp[i-1][j][k]

选 i 位置这个字符串，整体要保证字符 0 的个数不超过 j，字符 1 的个数不超过k，又因为选了 i 位置这个字符串，接下去取 0 ~ i - 1挑的时候，就要去掉 i 这个字符串中 字符串 0 的个数 和 字符串 1 的个数。然后加上选 i 位置字符串的个数。

注意 j - a，k - b 不一定存在，所以用之前要判断一下。

我们要的是最大长度，因此是两种情况的最大值

如果01背包问题都熟悉了，二维费用的01背包问题就是多加一个限制条件其他都一样。

3.初始化

初始化和之前一样，仅需考虑 i = 0 的情况就可以了，k = 0，j = 0 我们会特判不会越界的。

当 i = 0 表示字符串数组里没有字符串，如果数组没有字符串，想凑成字符串 0 的个数不超过 j，字符串 1 的个数不超过 k ，根本不能做到，不能做到就是一个空集，如果是空集，那最大个数全都是0

4.填表顺序

填dp[i][j][k]状态，要保证填 i 这一面 ， i - 1 那一面的值已经填好了，因此仅需保证 i 从小到大。j、k无论怎么变化什么顺序都可以。

5.返回值

dp[i][j][k] 表示：从前 i 个字符串中挑选，字符 0 的个数不超过 j，字符 1 的个数不超过 k，所有选法中，最长的长度。我们要的是从整个字符串中选，字符 0 的个数不超过 j，字符 1 的个数不超过 k，所有选法中，最长的长度。所以返回的是
dp[len][m][n]，len是字符串数组长度。

class Solution { public: int findMaxForm(vector<string>& strs, int m, int n) {  int len = strs.size(); vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(m + 1, vector<int>(n + 1))); for(int i = 1; i <= len; ++i) {  //统计一下字符串中 0 1 的个数 int a = 0, b = 0; for(auto ch : strs[i - 1]) {  if(ch == \'0\') a++; else b++