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

?474. 一和零

474.?一和零

题目描述：

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

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

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

?解题思路：

解题代码：

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.?盈利计划

题目描述：

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

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

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

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

?

解题思路：

解题代码：

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];
    }
};