LC 879. 盈利计划

题目描述

这是 LeetCode 上的 879. 盈利计划 ，难度为 困难。

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

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

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

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

示例 1：

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

示例 2：
1
2
3
4
输入：n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
输出：7
解释：至少产生 5 的利润，只要完成其中一种工作就行，所以该集团可以完成任何工作。
有 7 种可能的计划：(0)，(1)，(2)，(0,1)，(0,2)，(1,2)，以及 (0,1,2) 。

提示：

  • 1 <= n <= 100
  • 0 <= minProfit <= 100
  • 1 <= group.length <= 100
  • 1 <= group[i] <= 100
  • profit.length == group.length
  • 0 <= profit[i] <= 100

动态规划

这是一类特殊的多维费用背包问题。

将每个任务看作一个「物品」，完成任务所需要的人数看作「成本」，完成任务得到的利润看作「价值」。

其特殊在于存在一维容量维度需要满足「不低于」，而不是常规的「不超过」。这需要我们对于某些状态作等价变换。

定义 $f[i][j][k]$ 为考虑前 $i$ 件物品，使用人数不超过 $j$，所得利润至少为 $k$ 的方案数。

对于每件物品（令下标从 $1$ 开始），我们有「选」和「不选」两种决策：

  • 不选：显然有：
  • 选：首先需要满足人数达到要求（ $j >= group[i - 1]$ ），还需要考虑「至少利润」负值问题：
    如果直接令「利润维度」为 $k - profit[i - 1]$ 可能会出现负值，那么负值是否为合法状态呢？这需要结合「状态定义」来看，由于是「利润至少为 $k$」，因此属于「合法状态」，需要参与转移。
    由于我们没有设计动规数组存储「利润至少为负权」状态，我们需要根据「状态定义」做一个等价替换，将这个「状态」映射到 $f[i][j][0]$。这主要是利用所有的任务利润都为“非负数”，所以不可能出现利润为负的情况，这时候「利润至少为某个负数 $k$」的方案数其实是完全等价于「利润至少为 $0$」的方案数。

最终 $f[i][j][k]$ 为上述两种情况之和.

然后考虑「如何构造有效起始值」问题，还是结合我们的「状态定义」来考虑：

当不存在任何物品（任务）时，所得利用利润必然为 $0$（满足至少为 $0$），同时对人数限制没有要求。

因此可以让所有 $f[0][x][0] = 1$。

代码（一维空间优化代码见 P2）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    int mod = (int)1e9+7;
    public int profitableSchemes(int n, int min, int[] gs, int[] ps) {
        int m = gs.length;
        long[][][] f = new long[m + 1][n + 1][min + 1];
        for (int i = 0; i <= n; i++) f[0][i][0] = 1;            
        for (int i = 1; i <= m; i++) {
            int a = gs[i - 1], b = ps[i - 1];
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k <= min; k++) {
                    f[i][j][k] = f[i - 1][j][k];
                    if (j >= a) {
                        int u = Math.max(k - b, 0);
                        f[i][j][k] += f[i - 1][j - a][u];
                        f[i][j][k] %= mod;
                    }
                }
            }
        }
        return (int)f[m][n][min]; 
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    int mod = (int)1e9+7;
    public int profitableSchemes(int n, int min, int[] gs, int[] ps) {
        int m = gs.length;
        int[][] f = new int[n + 1][min + 1];
        for (int i = 0; i <= n; i++) f[i][0] = 1;            
        for (int i = 1; i <= m; i++) {
            int a = gs[i - 1], b = ps[i - 1];
            for (int j = n; j >= a; j--) {
                for (int k = min; k >= 0; k--) {
                    int u = Math.max(k - b, 0);
                    f[j][k] += f[j - a][u];
                    if (f[j][k] >= mod) f[j][k] -= mod;
                }
            }
        }
        return f[n][min]; 
    }
}

  • 时间复杂度：$O(m n min)$
  • 空间复杂度：$O(m n min)$

动态规划（作差法）

这个方案足足调了快一个小时 🤣

先是爆 long，然后转用高精度后被卡内存，最终改为滚动数组后勉强过了（不是，稳稳的过了，之前调得久是我把 N 多打了一位，写成 1005 了，N 不打错的话，不滚动也是能过的 😭😭😭 ）

基本思路是先不考虑最小利润 minProfit，求得所有只受「人数限制」的方案数 a，然后求得考虑「人数限制」同时，利润低于 minProfit（不超过 minProfit - 1）的所有方案数 b。

由 a - b 即是答案。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.math.BigInteger;
class Solution {
    static int N = 105;
    static BigInteger[][] f = new BigInteger[2][N]; 
    static BigInteger[][][] g = new BigInteger[2][N][N];
    static BigInteger mod = new BigInteger("1000000007");
    
    public int profitableSchemes(int n, int min, int[] gs, int[] ps) {
        int m = gs.length;

        for (int j = 0; j <= n; j++) {
            f[0][j] = new BigInteger("1"); 
            f[1][j] = new BigInteger("0"); 
        }
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= min; k++) {
                g[0][j][k] = new BigInteger("1"); 
                g[1][j][k] = new BigInteger("0"); 
            }
        }

        for (int i = 1; i <= m; i++) {
            int a = gs[i - 1], b = ps[i - 1];
            int x = i & 1, y = (i - 1) & 1;
            for (int j = 0; j <= n; j++) {
                f[x][j] = f[y][j];
                if (j >= a) {
                    f[x][j] = f[x][j].add(f[y][j - a]);
                } 
            }
        }
        if (min == 0) return (f[m&1][n]).mod(mod).intValue();

        for (int i = 1; i <= m; i++) {
            int a = gs[i - 1], b = ps[i - 1];
            int x = i & 1, y = (i - 1) & 1;
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k < min; k++) {
                    g[x][j][k] = g[y][j][k];
                    if (j - a >= 0 && k - b >= 0) {
                        g[x][j][k] = g[x][j][k].add(g[y][j - a][k - b]);
                    } 
                }
            }
        }

        return f[m&1][n].subtract(g[m&1][n][min - 1]).mod(mod).intValue();
    }
}

  • 时间复杂度：第一遍 DP 复杂度为 $O(m n)$；第二遍 DP 复杂度为 $O(m n min)$。整体复杂度为 $O(m n * min)$
  • 空间复杂度：$O(m n min)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.879 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。