英文原文
There is a group of n members, and a list of various crimes they could commit. The ith crime generates a profit[i] and requires group[i] members to participate in it. If a member participates in one crime, that member can't participate in another crime.
Let's call a profitable scheme any subset of these crimes that generates at least minProfit profit, and the total number of members participating in that subset of crimes is at most n.
Return the number of schemes that can be chosen. Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: n = 5, minProfit = 3, group = [2,2], profit = [2,3] Output: 2 Explanation: To make a profit of at least 3, the group could either commit crimes 0 and 1, or just crime 1. In total, there are 2 schemes.
Example 2:
Input: n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8] Output: 7 Explanation: To make a profit of at least 5, the group could commit any crimes, as long as they commit one. There are 7 possible schemes: (0), (1), (2), (0,1), (0,2), (1,2), and (0,1,2).
Constraints:
1 <= n <= 1000 <= minProfit <= 1001 <= group.length <= 1001 <= group[i] <= 100profit.length == group.length0 <= profit[i] <= 100
中文题目
集团里有 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 <= 1000 <= minProfit <= 1001 <= group.length <= 1001 <= group[i] <= 100profit.length == group.length0 <= profit[i] <= 100
通过代码
高赞题解
动态规划
这是一类特殊的多维费用背包问题。
将每个任务看作一个「物品」，完成任务所需要的人数看作「成本」，完成任务得到的利润看作「价值」。
其特殊在于存在一维容量维度需要满足「不低于」，而不是常规的「不超过」。这需要我们对于某些状态作等价变换。
定义 $f[i][j][k]$ 为考虑前 $i$ 件物品，使用人数不超过 $j$，所得利润至少为 $k$ 的方案数。
对于每件物品（令下标从 $1$ 开始），我们有「选」和「不选」两种决策：
- 不选：显然有：
$$f[i - 1][j][k]$$
- 选：首先需要满足人数达到要求（ $j >= group[i - 1]$ ），还需要考虑「至少利润」负值问题：
如果直接令「利润维度」为 $k - profit[i - 1]$ 可能会出现负值，那么负值是否为合法状态呢？这需要结合「状态定义」来看，由于是「利润至少为 $k$」，因此属于「合法状态」，需要参与转移。
由于我们没有设计动规数组存储「利润至少为负权」状态，我们需要根据「状态定义」做一个等价替换，将这个「状态」映射到 $f[i][j][0]$。这主要是利用所有的任务利润都为“非负数”，所以不可能出现利润为负的情况，这时候「利润至少为某个负数 $k$」的方案数其实是完全等价于「利润至少为 $0$」的方案数。
$$f[i - 1][j - group[i - 1]][\max(k - profit[i - 1], 0)]$$
最终 $f[i][j][k]$ 为上述两种情况之和.
然后考虑「如何构造有效起始值」问题，还是结合我们的「状态定义」来考虑：
当不存在任何物品（任务）时，所得利用利润必然为 $0$（满足至少为 $0$），同时对人数限制没有要求。
因此可以让所有 $f[0][x][0] = 1$。
代码（一维空间优化代码见 P2）：
[]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]; if (f[i][j][k] >= mod) f[i][j][k] -= mod; } } } } return (int)f[m][n][min]; } }
[]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 即是答案。
代码：
[]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(n * min)$
背包问题（目录）
01背包 : 背包问题 第一讲
- 【练习】01背包 : 背包问题 第二讲（416. 分割等和子集）
- 【学习&练习】01背包 : 背包问题 第三讲（416. 分割等和子集）
完全背包 : 背包问题 第四讲
- 【练习】完全背包 : 背包问题 第五讲（279. 完全平方数）
- 【练习】完全背包 : 背包问题 第六讲（322. 零钱兑换）
- 【练习】完全背包 : 背包问题 第七讲（518. 零钱兑换 II）
多重背包 : 背包问题 第八讲
多重背包（优化篇）
混合背包 : 背包问题 第十一讲
- 【练习】混合背包
分组背包
- 【练习】分组背包
多维背包
- 【练习】多维背包 : 背包问题 第 * 讲（474. 一和零）
- 【练习】多维背包 : 背包问题 第 * 讲（879. 盈利计划）
树形背包
- 【练习】树形背包
背包求方案数
- 【练习】背包求方案数 : 背包问题 第 * 讲（494. 目标和）
- 【练习】背包求方案数 : 背包问题 第 * 讲（879. 盈利计划）
背包求具体方案
- 【练习】背包求具体方案 : 背包问题 第 * 讲（1049. 最后一块石头的重量 II）
泛化背包
- 【练习】泛化背包
最后
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/
也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 21963 | 39698 | 55.3% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
