leetcode-879-盈利计划

盈利计划

题面

leetcode题目

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

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

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

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

example

输入：\(n = 5\), \(minProfit = 3\), \(group = [2,2]\), \(profit = [2,3]\)
输出：\(2\)
解释：至少产生 \(3\) 的利润，该集团可以完成工作 \(0\) 和工作 \(1\) ，或仅完成工作 \(1\) 。 总的来说，有两种计划。

数据范围

• \(1 \leq n \leq 100\)
• \(0 \leq minProfit \leq 100\)
• \(1 \leq group.length \leq 100\)
• \(1 \leq group[i] \leq 100\)
• \(profit.length == group.length\)
• \(0 \leq profit[i] \leq 100\)

题解

总体思路

整体可以考虑为背包容量为\(n\)，价值大于等于\(minProfit\)的二维背包。
\(dp[i][j][k]\)表示在选择完第\(i\)个工作后，当前盈利\(j\)且员工数为\(k\)的计划数量，那么结果为\(\sum_{j=minProfit,k=0}^{j<= total, k<= n} dp[group.length][j][k]\)，其中\(total=\sum_{i=0}^{profit.length} profit[i]\)。
转移方程也是显然的： \[ dp[i][j][k] = \left\{ \begin{array}{rcl} 1 & & {i = 0 \vee j = 0 \vee k = 0} \\ dp[i-1][j][k] + dp[i-1][j - profit[i]][k - group[i]] & & {j - profit[i] \geq 0 \land k - group[i] \geq 0} \\ dp[i-1][j][k] & & {others} \end{array} \right. \] 这里需要用滚动数组优化一下空间。

一个小优化

实际上我们可以考虑求利润小于\(minProfit\)的组合数，再求出背包体积不超过\(n\)的方案数，可以反推出题设需要的数量。

代码

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define _DEBUG
#define LL long long

class Solution
{
public:
    const int MOD = 1e9 + 7;
    int profitableSchemes(int n, int minProfit, vector<int> &group, vector<int> &profit)
    {
        const int len = group.size();
        int MAX = 0;
        for (int i = 0; i < len; i++)
        {
            MAX += profit[i];
        }
        MAX += 1;
        LL dpPre[MAX][n + 1];
        LL dp[MAX][n + 1];
        memset(dp, 0, sizeof(dp));
        memset(dpPre, 0, sizeof(dpPre));
        dpPre[0][0] = 1;
        for (int i = 1; i <= len; i++)
        {
            int v = profit[i - 1];
            int t = group[i - 1];
            for (int k = 0; k < MAX; k++)
            {
                for (int j = 0; j <= n; j++)
                {
                    dp[k][j] += dpPre[k][j];
                    if (k - v >= 0 && j - t >= 0)
                    {
                        dp[k][j] += dpPre[k - v][j - t];
                    }
                    if (dp[k][j] > MOD)
                    {
                        dp[k][j] %= MOD;
                    }
#ifdef _DEBUG
                    if (dp[k][j] != 0)
                    {
                        cout << "i: " << i << " k: " << k << " j: " << j << " dp[k][j]: " << dp[k][j] << endl;
                    }
#endif
                }
            }
            memcpy(dpPre, dp, sizeof(dpPre));
            memset(dp, 0, sizeof(dp));
        }
        LL sum = 0;
        for (int i = minProfit; i < MAX; i++)
        {
            for (int j = 0; j <= n; j++)
            {
#ifdef _DEBUG
                if (dpPre[i][j] != 0)
                {
                    cout << "i: " << i << " j: " << j << " dp: " << dpPre[i][j] << endl;
                }
#endif
                sum += dpPre[i][j];
                if (sum > MOD)
                {
                    sum %= MOD;
                }
            }
        }
        return sum % MOD;
    }
};

// for test
int main()
{
    Solution s;

    vector<int> g1{2, 2};
    vector<int> p1{2, 3};
    cout << s.profitableSchemes(5, 3, g1, p1) << endl;

    vector<int> g2{2, 3, 5};
    vector<int> p2{6, 7, 8};
    cout << s.profitableSchemes(10, 5, g2, p2) << endl;

    vector<int> g3{2, 2, 2, 2, 2};
    vector<int> p3{1, 2, 1, 1, 0};
    cout << s.profitableSchemes(1, 1, g3, p3) << endl;
    return 0;
}