【算法挨揍日记】day45——474. 一和零、879. 盈利计划

素颜马尾好姑娘i 2024-02-05 21:24 12阅读 0赞

## 474. 一和零 ##

[474. 一和零][474.]

### 题目描述： ###

给你一个二进制字符串数组 `strs` 和两个整数 `m` 和 `n` 。

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

如果 `x` 的所有元素也是 `y` 的元素，集合 `x` 是集合 `y` 的 **子集** 。![5e3e8d05c10d467b91a68c19a00744b8.png][]

### 解题思路： ###

算法思路：

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

i.  在⼀些物品中「挑选」⼀些出来，然后在满⾜某个「限定条件」下，解决⼀些问题，⼤概率

是背包模型；

ii.  由于每⼀个物品都只有  1  个，因此是⼀个「01 背包问题」。

但是，我们发现这⼀道题⾥⾯有「两个限制条件」。因此是⼀个「⼆维费⽤的 01 背包问题」。那

么我们定义状态表⽰的时候，来⼀个三维  dp  表，把第⼆个限制条件加上即可。

1.  状态表⽰：

dp\[i\]\[j\]\[k\]  表⽰：从前  i  个字符串中挑选，字符  0  的个数不超过  j  ，字符  1  的个数不

超过  k  ，所有的选法中，最⼤的⻓度。

2.  状态转移⽅程：

线性  dp  状态转移⽅程分析⽅式，⼀般都是「根据最后⼀步」的状况，来分情况讨论。为了⽅便

叙述，我们记第  i  个字符中，字符  0  的个数为  a  ，字符  1  的个数为  b  ：

i.  不选第  i  个字符串：相当于就是去前  i - 1  个字符串中挑选，并且字符  0  的个数不超

过  j  ，字符  1  的个数不超过  k  。此时的最⼤⻓度为  dp\[i\]\[j\]\[k\] = dp\[i - 1\]

\[j\]\[k\]  ；

ii.  选择第  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\]\[j\]\[k\], dp\[i - 1\]\[j - a\]

\[k - b\] + 1)  。

3.  初始化：

当没有字符串的时候，没有⻓度，因此初始化为  0  即可。

4.  填表顺序：

保证第⼀维的循环「从⼩到⼤」即可。

5.  返回值：

根据「状态表⽰」，我们返回  dp\[len\]\[m\]\[n\]  。

其中  len  表⽰字符串数组的⻓度。

6.  空间优化：

所有的「背包问题」，都可以进⾏空间上的优化。

对于「⼆维费⽤的 01 背包」类型的，我们的优化策略是：

i.  删掉第⼀维；

ii.  修改第⼆层以及第三层循环的遍历顺序即可

### 解题代码： ###

class Solution {
    public:
        int f(string s,char ch)
        {
            int ret=0;
            for(int i=0;i<=s.size();i++)
                if(s[i]==ch)    ret++;
            return ret;
        }
        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++)
            {
                for(int j=0;j<=m;j++)
                {
                    for(int k=0;k<=n;k++)
                    {
                        dp[i][j][k]=dp[i-1][j][k];
                        int a=f(strs[i-1],'0');//0的个数
                        int b=f(strs[i-1],'1');//1的个数
                        if(j>=a&&k>=b)
                        dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-a][k-b]+1);
                    }
                }
            }
            return dp[len][m][n];
        }
    };

## 879. 盈利计划 ##

[879. 盈利计划][879.]

### 题目描述： ###

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

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

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

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

### ![f9ca2024a3fc4322b9dd049aabdca5e4.png][] ###

### 解题思路： ###

算法思路：

这道题⽬⾮常难读懂，但是如果结合例⼦多读⼏遍，你就会发现是⼀个经典的「⼆维费⽤的背包问

题」。因此我们可以仿照「⼆维费⽤的背包」来定义状态表⽰。

1.  状态表⽰：

dp\[i\]\[j\]\[k\]  表⽰：从前  i  个计划中挑选，总⼈数不超过  j  ，总利润⾄少为  k  ，⼀共有多

少种选法。

注意注意注意，这道题⾥⾯出现了⼀个「⾄少」，和我们之前做过的背包问题不⼀样。因此，我们

在分析「状态转移⽅程」的时候要结合实际情况考虑⼀下。

2.  状态转移⽅程：

⽼规矩，根据「最后⼀个位置」的元素，结合题⽬的要求，我们有「选择」最后⼀个元素或者「不

选择」最后⼀个元素两种策略：

i.  不选  i  位置的计划：那我们只能去前  i - 1  个计划中挑选，总⼈数不超过  j  ，总利润

⾄少为  k  。此时⼀共有  dp\[i - 1\]\[j\]\[k\]  种选法；

ii.  选择  i  位置的计划：那我们在前  i - 1  个计划中挑选的时候，限制就变成了，总⼈数不

超过  j - g\[i\]  ，总利润⾄少为  k - p\[i\]  。此时⼀共有  dp\[i - 1\]\[j - g\[i\]\]

\[k - p\[i\]\]  。

第⼆种情况下有两个细节需要注意：

1.  j - g\[i\] < 0  ：此时说明  g\[i\]  过⼤，也就是⼈数过多。因为我们的状态表⽰要

求⼈数是不能超过  j  的，因此这个状态是不合法的，需要舍去。

2.  k - p\[i\] < 0  ：此时说明  p\[i\]  过⼤，也就是利润太⾼。但是利润⾼，不正是我

们想要的嘛？所以这个状态「不能舍去」。但是问题来了，我们的  dp  表是没有负数的

下标的，这就意味着这些状态我们⽆法表⽰。其实，根本不需要负的下标，我们根据实

际情况来看，如果这个任务的利润已经能够达标了，我们仅需在之前的任务中，挑选出

来的利润⾄少为  0  就可以了。因为实际情况不允许我们是负利润，那么负利润就等价

于利润⾄少为  0  的情况。所以说这种情况就等价于  dp\[i\]\[j\]\[0\]  ，我们可以对  k

\- p\[i\]  的结果与  0  取⼀个  max  。

综上，我们的状态转移⽅程为：

dp\[i\]\[j\]\[k\] = dp\[i - 1\]\[j\]\[k\] + dp\[i - 1\]\[j - g\[i - 1\]\]\[max(0, k

\- p\[i - 1\])\]  。

3.  初始化：

当没有任务的时候，我们的利润为  0  ，此时⽆论⼈数限制为多少，我们都能找到⼀个「空集」的

⽅案。

因此初始化  dp\[0\]\[j\]\[0\]  的位置为  1  ，其中  0 <= j <= n  。

4.  填表顺序：

根据「状态转移⽅程」，我们保证  i  从⼩到⼤即可。

5.  返回值：

根据「状态表⽰」，我们返回  dp\[len\]\[m\]\[n\]  。

其中  len  表⽰字符串数组的⻓度。

6.  空间优化：

所有的「背包问题」，都可以进⾏空间上的优化。

对于「⼆维费⽤的 01 背包」类型的，我们的优化策略是：

i.  删掉第⼀维；

ii.  修改第⼆层以及第三层循环的遍历顺序即可。

### 解题代码： ###

class Solution {
    public:
        int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
            const int MOD=1e9+7;
            int len=group.size();
            vector<vector<vector<int>>>dp(len+1,vector<vector<int>>(n+1,vector<int>(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]][max(k-profit[i-1],0)];
                        dp[i][j][k]%=MOD;
                    }
                }
            }
            return dp[len][n][minProfit];
        }
    };

[474.]: https://leetcode.cn/problems/ones-and-zeroes/
[5e3e8d05c10d467b91a68c19a00744b8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/3bc6dcc41de74ef0a50ac2a190a6a3af.png
[879.]: https://leetcode.cn/problems/profitable-schemes/
[f9ca2024a3fc4322b9dd049aabdca5e4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/5aee86dfa7df4da8b6b1ef3a0d33f136.png