题目描述
这是 LeetCode 上的 879. 盈利计划 ，难度为 困难。
Tag : 「动态规划」、「容斥原理」、「数学」、「背包问题」、「多维背包」
集团里有 n 名员工，他们可以完成各种各样的工作创造利润。
第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。
工作的任何至少产生 minProfit 利润的子集称为 盈利计划 。并且工作的成员总数最多为 n 。
有多少种计划可以选择？因为答案很大，所以 返回结果模 10^9 + 7 109+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
动态规划
这是一类特殊的多维费用背包问题。
将每个任务看作一个「物品」，完成任务所需要的人数看作「成本」，完成任务得到的利润看作「价值」。
其特殊在于存在一维容量维度需要满足「不低于」，而不是常规的「不超过」。这需要我们对于某些状态作等价变换。
定义 f[i][j][k]f[i][j][k] 为考虑前 ii 件物品，使用人数不超过 jj，所得利润至少为 kk 的方案数。
对于每件物品（令下标从 11 开始），我们有「选」和「不选」两种决策：
- 不选：显然有：
f[i - 1][j][k]f[i−1][j][k]
- 选：首先需要满足人数达到要求（ j >= group[i - 1]j>=group[i−1] ），还需要考虑「至少利润」负值问题： 如果直接令「利润维度」为 k - profit[i - 1]k−profit[i−1] 可能会出现负值，那么负值是否为合法状态呢？这需要结合「状态定义」来看，由于是「利润至少为 kk」，因此属于「合法状态」，需要参与转移。 由于我们没有设计动规数组存储「利润至少为负权」状态，我们需要根据「状态定义」做一个等价替换，将这个「状态」映射到 f[i][j][0]f[i][j][0]。这主要是利用所有的任务利润都为“非负数”，所以不可能出现利润为负的情况，这时候「利润至少为某个负数 kk」的方案数其实是完全等价于「利润至少为 00」的方案数。
f[i - 1][j - group[i - 1]][\max(k - profit[i - 1], 0)]f[i−1][j−group[i−1]][max(k−profit[i−1],0)]
最终 f[i][j][k]f[i][j][k] 为上述两种情况之和.
然后考虑「如何构造有效起始值」问题，还是结合我们的「状态定义」来考虑：
当不存在任何物品（任务）时，所得利用利润必然为 00（满足至少为 00），同时对人数限制没有要求。
因此可以让所有 f[0][x][0] = 1f[0][x][0]=1。
代码：
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]; } } 复制代码
- 时间复杂度：O(m * n * min)O(m∗n∗min)
- 空间复杂度：O(m * n * min)O(m∗n∗min)
动态规划（作差法）
这个方案足足调了快一个小时 🤣
先是爆 long，然后转用高精度后被卡内存，最终改为滚动数组后勉强过了（不是，稳稳的过了，之前调得久是我把 N 多打了一位，写成 1005 了，N 不打错的话，不滚动也是能过的 😭😭😭 ）
基本思路是先不考虑最小利润 minProfit，求得所有只受「人数限制」的方案数 a，然后求得考虑「人数限制」同时，利润低于 minProfit（不超过 minProfit - 1）的所有方案数 b。
由 a - b 即是答案。
代码：
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)O(m∗n)；第二遍DP复杂度为 O(m * n * min)O(m∗n∗min)。整体复杂度为 O(m * n * min)O(m∗n∗min) - 空间复杂度：O(m * n * min)O(m∗n∗min)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.879 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
