每日OJ题_其它背包问题①_力扣474. 一和零（二维费用01背包）

目录

力扣474. 一和零

解析代码

代码优化

---

力扣474. 一和零

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 。

提示：

• 1 <= strs.length <= 600
• 1 <= strs[i].length <= 100
• strs[i] 仅由 '0' 和 '1' 组成
• 1 <= m, n <= 100

class Solution {
public:
    int findMaxForm(vector& strs, int m, int n) {
 
    }
};

---

解析代码

先看能不能将问题转化成我们熟悉的题型。

        在一些物品中挑选一些出来，然后在满足某个限定条件下，解决一些问题，大概率是背包模型， 由于每一个物品都只有 1 个，因此是一个01 背包问题。 但是发现这一道题里面有两个限制条件。因此是一个二维费用的 01 背包问题。那么定义状态表示的时候，创建一个三维 dp 表，把第二个限制条件加上即可。

        二维费用的背包问题是指：对于每件物品，具有两种不同的费用，选择这件物品必须同时付出这两种代价，对于每种代价都有一个可付出的最大值（例：背包容量，问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2，第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值（两种背包容量）分别为V和U。物品的价值为w[i]。）

        故：对于01背包问题、完全背包问题和多重背包问题的方法都完全可以使用，只不过增加一个代价。

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

状态转移方程：

        线性 dp 状态转移方程分析方式，一般都是根据最后一步的状况，来分情况讨论。为了方便叙述，记第 i 个字符中，字符 0 的个数为 a ，字符 1 的个数为 b ：

• 不选第 i 个字符串：相当于就是去前 i - 1 个字符串中挑选，并且字符 0 的个数不超 过 j ，字符 1 的个数不超过 k 。此时的最大长度为 dp[i][j][k] = dp[i - 1] [j][k] 。
• 选择第 i 个字符串：那么接下来仅需在前 i - 1 个字符串里面，挑选出来字符 0 的 个数不超过 j - a ，字符 1 的个数不超过 k - b 的最长长度，然后在这个长度后面加 上字符串 i 即可。此时 dp[i][j][k] = dp[i - 1][j - a][k - b] + 1 。 但是这种状态不⼀定存在，因此需要特判⼀下。

综上，状态转移方程为：dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - a] [k - b] + 1) ;

初始化： 每一维多开一个空间方便初始化，当 第一维i为0 即没有字符串的时候，没有长度，因此初始化为 0 即可。

填表顺序： 保证第一维i 从小到大即可。

返回值： 根据状态表示，返回 dp[len][m][n] ，其中 len 表示字符串数组的长度。

class Solution {
public:
    int findMaxForm(vector& strs, int m, int n) {
        // dp[i][j][k] 表示：从前 i 个字符串中挑选，字符 0 的个数不超过 j ,
        // 字符 1 的个数不超过 k ，所有的选法中，最大的长度
        int len = strs.size();
        vectorint>>> dp(len + 1, vectorint>>(m + 1, vector<int>(n + 1, 0)));
        for(int i = 1; i <= len; ++i)
        {
            int a = 0, b = 0;
            for(auto& e : strs[i - 1]) // 统计0和1的个数
            {
                if(e == '0')
                    ++a;    
                else
                    ++b;
            }
            for(int j = 0; j <= m; ++j)
            {
                for(int k = 0; k <= n; ++k)
                {
                    if(j >= a && k >= b)
                        dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - a][k - b] + 1) ;
                    else
                        dp[i][j][k] = dp[i - 1][j][k];
                }
            }
        }
        return dp[len][m][n];
    }
};

---

代码优化

        所有的背包问题，都可以进行空间上的优化。 对于二维费用的 01 背包问题，优化还是和之前的01背包类似，删掉第一维，然后修改其他维度的遍历顺序：

class Solution {
public:
    int findMaxForm(vector& strs, int m, int n) {
        // dp[i][j][k] 表示：从前 i 个字符串中挑选，字符 0 的个数不超过 j ,
        // 字符 1 的个数不超过 k ，所有的选法中，最大的长度
        int len = strs.size();
        vectorint>> dp(m + 1, vector<int>(n + 1, 0));
        for(int i = 1; i <= len; ++i)
        {
            int a = 0, b = 0;
            for(auto& e : strs[i - 1]) // 统计0和1的个数
            {
                if(e == '0')
                    ++a;    
                else
                    ++b;
            }
            for(int j = m; j >= 0; --j)
            {
                for(int k = n; k >= 0; --k)
                {
                    if(j >= a && k >= b)
                        dp[j][k] = max(dp[j][k], dp[j - a][k - b] + 1) ;
                    else
                        dp[j][k] = dp[j][k];
                }
            }
        }
        return dp[m][n];
    }
};

​​​​​​​