0879-盈利计划

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:26 2023-09-13 16:06:26 Updated    

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

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

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

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

示例 1：

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

示例 2：

**输入：** 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

方法一：动态规划

本题与经典背包问题非常相似。两者不同点在于经典背包问题只有一种容量限制，而本题却有两种限制：集团员工人数上限 n，以及工作产生的利润下限 minProfit。

通过经典背包问题的练习，我们已知经典背包问题可以使用二维动态规划求解：两个维度分别代表物品和容量的限制标准。对于本题上述的两种限制，我们可以想到使用三维动态规划求解。本题解法的三个维度分别为：当前可选择的工作，已选择的小组员工人数，以及目前状态的工作获利下限。

根据上述分析，我们可以定义一个三维数组 dp 作为动态规划的状态，其中 dp}[i][j][k] 表示在前 i 个工作中选择了 j 个员工，并且满足工作利润至少为 k 的情况下的盈利计划的总数目。假设 group 数组长度为 len，那么不考虑取模运算的情况下，最终答案为：

\sum_{i=0}^{n}\textit{dp}[\textit{len}][i][\textit{minProfit}]

所以我们可以新建一个三维数组 dp}[\textit{len} + 1][n + 1][\textit{minProfit} + 1]，初始化 dp}[0][0][0] = 1。接下来分析状态转移方程，对于每个工作 i，我们根据当前工作人数上限 j，有能够开展当前工作和无法开展当前工作两种情况：

  • 如果无法开展当前工作 i，那么显然：

    \textit{dp}[i][j][k] = \textit{dp}[i - 1][j][k]

  • 如果能够开展当前工作 i，设当前小组人数为 group}[i]，工作获利为 profit}[i]，那么不考虑取模运算的情况下，则有：

    \textit{dp}[i][j][k] = \textit{dp}[i - 1][j][k] + \textit{dp}[i - 1][j - \textit{group}[i]][\max(0, k - \textit{profit}[i])]

由于我们定义的第三维是工作利润至少为 k 而不是 工作利润恰好为 k，因此上述状态转移方程中右侧的第三维是 \max(0, k - \textit{profit}[i]) 而不是 k - \textit{profit}[i]。读者可以思考这一步的妙处所在。

根据上述思路，参考代码如下：

[sol11-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int len = group.length, MOD = (int)1e9 + 7;
        int[][][] dp = new int[len + 1][n + 1][minProfit + 1];
        dp[0][0][0] = 1;
        for (int i = 1; i <= len; i++) {
            int members = group[i - 1], earn = profit[i - 1];
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k <= minProfit; k++) {
                    if (j < members) {
                        dp[i][j][k] = dp[i - 1][j][k];
                    } else {
                        dp[i][j][k] = (dp[i - 1][j][k] + dp[i - 1][j - members][Math.max(0, k - earn)]) % MOD;
                    }
                }
            }
        }
        int sum = 0;
        for (int j = 0; j <= n; j++) {
            sum = (sum + dp[len][j][minProfit]) % MOD;
        }
        return sum;
    }
}
[sol11-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public int ProfitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int len = group.Length, MOD = (int)1e9 + 7;
        int[,,] dp = new int[len + 1, n + 1, minProfit + 1];
        dp[0, 0, 0] = 1;
        for (int i = 1; i <= len; i++) {
            int members = group[i - 1], earn = profit[i - 1];
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k <= minProfit; k++) {
                    if (j < members) {
                        dp[i, j, k] = dp[i - 1, j, k];
                    } else {
                        dp[i, j, k] = (dp[i - 1, j, k] + dp[i - 1, j - members, Math.Max(0, k - earn)]) % MOD;
                    }
                }
            }
        }
        int sum = 0;
        for (int j = 0; j <= n; j++) {
            sum = (sum + dp[len, j, minProfit]) % MOD;
        }
        return sum;
    }
}
[sol11-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var profitableSchemes = function(n, minProfit, group, profit) {
    const len = group.length, MOD = 1e9 + 7;
    const dp = new Array(len + 1).fill(0).map(() => new Array(n + 1).fill(0).map(() => new Array(minProfit + 1).fill(0)));
    dp[0][0][0] = 1;
    for (let i = 1; i <= len; i++) {
        const members = group[i - 1], earn = profit[i - 1];
        for (let j = 0; j <= n; j++) {
            for (let k = 0; k <= minProfit; k++) {
                if (j < members) {
                    dp[i][j][k] = dp[i - 1][j][k];
                } else {
                    dp[i][j][k] = (dp[i - 1][j][k] + dp[i - 1][j - members][Math.max(0, k - earn)]) % MOD;
                }
            }
        }
    }
    let sum = 0;
    for (let j = 0; j <= n; j++) {
        sum = (sum + dp[len][j][minProfit]) % MOD;
    }
    return sum;
};
[sol11-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:
        MOD = 10**9 + 7
        
        length = len(group)
        dp = [[[0] * (minProfit + 1) for _ in range(n + 1)] for _ in range(length + 1)]
        dp[0][0][0] = 1
        for i in range(1, length + 1):
            members, earn = group[i - 1], profit[i - 1]
            for j in range(n + 1):
                for k in range(minProfit + 1):
                    if j < members:
                        dp[i][j][k] = dp[i - 1][j][k]
                    else:
                        dp[i][j][k] = (dp[i - 1][j][k] + dp[i - 1][j - members][max(0, k - earn)]) % MOD
        
        total = sum(dp[length][j][minProfit] for j in range(n + 1))
        return total % MOD
[sol11-C++]
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
class Solution {
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        int len = group.size(), MOD = (int)1e9 + 7;
        vector<vector<vector<int>>> dp(len + 1, vector<vector<int>>(n + 1, vector<int>(minProfit + 1)));
        dp[0][0][0] = 1;
        for (int i = 1; i <= len; i++) {
            int members = group[i - 1], earn = profit[i - 1];
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k <= minProfit; k++) {
                    if (j < members) {
                        dp[i][j][k] = dp[i - 1][j][k];
                    } else {
                        dp[i][j][k] = (dp[i - 1][j][k] + dp[i - 1][j - members][max(0, k - earn)]) % MOD;
                    }
                }
            }
        }
        int sum = 0;
        for (int j = 0; j <= n; j++) {
            sum = (sum + dp[len][j][minProfit]) % MOD;
        }
        return sum;
    }
};
[sol11-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int profitableSchemes(int n, int minProfit, int* group, int groupSize, int* profit, int profitSize) {
    int len = groupSize, MOD = (int)1e9 + 7;
    int dp[len + 1][n + 1][minProfit + 1];
    memset(dp, 0, sizeof(dp));
    dp[0][0][0] = 1;
    for (int i = 1; i <= len; i++) {
        int members = group[i - 1], earn = profit[i - 1];
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= minProfit; k++) {
                if (j < members) {
                    dp[i][j][k] = dp[i - 1][j][k];
                } else {
                    dp[i][j][k] = (dp[i - 1][j][k] + dp[i - 1][j - members][(int)fmax(0, k - earn)]) % MOD;
                }
            }
        }
    }
    int sum = 0;
    for (int j = 0; j <= n; j++) {
        sum = (sum + dp[len][j][minProfit]) % MOD;
    }
    return sum;
}
[sol11-Golang]
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
func profitableSchemes(n, minProfit int, group, profit []int) (sum int) {
    const mod int = 1e9 + 7
    ng := len(group)
    dp := make([][][]int, ng+1)
    for i := range dp {
        dp[i] = make([][]int, n+1)
        for j := range dp[i] {
            dp[i][j] = make([]int, minProfit+1)
        }
    }
    dp[0][0][0] = 1
    for i, members := range group {
        earn := profit[i]
        for j := 0; j <= n; j++ {
            for k := 0; k <= minProfit; k++ {
                if j < members {
                    dp[i+1][j][k] = dp[i][j][k]
                } else {
                    dp[i+1][j][k] = (dp[i][j][k] + dp[i][j-members][max(0, k-earn)]) % mod
                }
            }
        }
    }
    for _, d := range dp[ng] {
        sum = (sum + d[minProfit]) % mod
    }
    return
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

可以发现 dp}[i][j][k] 仅与 dp}[i - 1][..][..] 有关，所以本题可以用二维动态规划解决。当采用二维动态规划解法时，对于最小工作利润为 0 的情况，无论当前在工作的员工有多少人，我们总能提供一种方案，所以初始化 dp}[i][0] = 1。此外，降维之后 dp 数组的遍历顺序应为逆序，与背包问题降维解法类似，因为这样才能保证求状态 dp}[j][k] 时, 用到的 dp}[j - \textit{members}][\max(0, k - \textit{earn})] 是上一时刻的值，而正序遍历则会改写该值。参考代码如下：

[sol12-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int[][] dp = new int[n + 1][minProfit + 1];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }
        int len = group.length, MOD = (int)1e9 + 7;
        for (int i = 1; i <= len; i++) {
            int members = group[i - 1], earn = profit[i - 1];
            for (int j = n; j >= members; j--) {
                for (int k = minProfit; k >= 0; k--) {
                    dp[j][k] = (dp[j][k] + dp[j - members][Math.max(0, k - earn)]) % MOD;
                }
            }
        }
        return dp[n][minProfit];
    }
}
[sol12-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public int ProfitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int[,] dp = new int[n + 1, minProfit + 1];
        for (int i = 0; i <= n; i++) {
            dp[i, 0] = 1;
        }
        int len = group.Length, MOD = (int)1e9 + 7;
        for (int i = 1; i <= len; i++) {
            int members = group[i - 1], earn = profit[i - 1];
            for (int j = n; j >= members; j--) {
                for (int k = minProfit; k >= 0; k--) {
                    dp[j, k] = (dp[j, k] + dp[j - members, Math.Max(0, k - earn)]) % MOD;
                }
            }
        }
        return dp[n, minProfit];
    }
}
[sol12-Python3]
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:
        MOD = 10**9 + 7
        dp = [[0] * (minProfit + 1) for _ in range(n + 1)]
        for i in range(0, n + 1):
            dp[i][0] = 1
        for earn, members in zip(profit, group):
            for j in range(n, members - 1, -1):
                for k in range(minProfit, -1, -1):
                    dp[j][k] = (dp[j][k] + dp[j - members][max(0, k - earn)]) % MOD;
        return dp[n][minProfit]
[sol12-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var profitableSchemes = function(n, minProfit, group, profit) {
    const dp = new Array(n + 1).fill(0).map(() => new Array(minProfit + 1).fill(0));
    for (let i = 0; i <= n; i++) {
        dp[i][0] = 1;
    }
    const len = group.length, MOD = 1e9 + 7;
    for (let i = 1; i <= len; i++) {
        const members = group[i - 1], earn = profit[i - 1];
        for (let j = n; j >= members; j--) {
            for (let k = minProfit; k >= 0; k--) {
                dp[j][k] = (dp[j][k] + dp[j - members][Math.max(0, k - earn)]) % MOD;
            }
        }
    }
    return dp[n][minProfit];
};
[sol12-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        vector<vector<int>> dp(n + 1, vector<int>(minProfit + 1));
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }
        int len = group.size(), MOD = (int)1e9 + 7;
        for (int i = 1; i <= len; i++) {
            int members = group[i - 1], earn = profit[i - 1];
            for (int j = n; j >= members; j--) {
                for (int k = minProfit; k >= 0; k--) {
                    dp[j][k] = (dp[j][k] + dp[j - members][max(0, k - earn)]) % MOD;
                }
            }
        }
        return dp[n][minProfit];
    }
};
[sol12-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int profitableSchemes(int n, int minProfit, int* group, int groupSize, int* profit, int profitSize) {
    int dp[n + 1][minProfit + 1];
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 1;
    }
    int len = groupSize, MOD = (int)1e9 + 7;
    for (int i = 1; i <= len; i++) {
        int members = group[i - 1], earn = profit[i - 1];
        for (int j = n; j >= members; j--) {
            for (int k = minProfit; k >= 0; k--) {
                dp[j][k] = (dp[j][k] + dp[j - members][(int)fmax(0, k - earn)]) % MOD;
            }
        }
    }
    return dp[n][minProfit];
}
[sol12-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func profitableSchemes(n, minProfit int, group, profit []int) (sum int) {
    const mod int = 1e9 + 7
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, minProfit+1)
        dp[i][0] = 1
    }
    for i, members := range group {
        earn := profit[i]
        for j := n; j >= members; j-- {
            for k := minProfit; k >= 0; k-- {
                dp[j][k] = (dp[j][k] + dp[j-members][max(0, k-earn)]) % mod
            }
        }
    }
    return dp[n][minProfit]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

复杂度分析

  • 时间复杂度：O(\textit{len} \times n \times \textit{minProfit})，其中 len 为数组 group 的长度。
    动态规划需要计算的状态总数是 O(\textit{len} \times n \times \textit{minProfit})，每个状态的值需要 O(1) 的时间计算。

  • 空间复杂度：O(n \times \textit{minProfit})。
    使用空间优化的实现，需要创建 n + 1 行，minProfit} + 1 列的二维数组 dp。

 Comments
On this page
0879-盈利计划