LeetCode 879. 盈利计划
集团里有 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) 。method
dp[i][j][k]：前面i份工作，刚好j个人，利润至少为k的方案数
相当于是两个维度的背包，且第二个维度是价值（利润）至少为某个值，而不是普通的不超过某个值（背包容量）
对于每件物品（令下标从 1 开始），我们有「选」和「不选」两种决策：
不选：显然有：
选：首先需要满足人数达到要求（j >= group[i - 1]），还需要考虑「至少利润」负值问题
如果直接令「利润维度」为 k - profit[i - 1] 可能会出现负值，那么负值是否为合法状态呢？这需要结合「状态定义」来看，由于是「利润至少为 k」，因此属于「合法状态」，需要参与转移。
由于我们没有设计动规数组存储「利润至少为负权」状态，我们需要根据「状态定义」做一个等价替换，将这个「状态」映射到 f[i][j][0]。这主要是利用所有的任务利润都为“非负数”，所以不可能出现利润为负的情况，这时候「利润至少为某个负数 k」的方案数其实是完全等价于「利润至少为 0」的方案数。
如果当前的利润pro>=k，已经满足要求了，那之后的工作利润只要0就行
如果当前的利润pro<k，说明后面的工作还需要k-pro的利润
这里所说的员工最多为n，意思是没要求所有人都要有工作，也就是背包容量上限为n，这样就需要把容量0-n的情况都考虑，也就是累加起来
初始化：前面0份工作，刚好0人的时候，利润至少为0的方案数是1
int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
int MOD = 1e9 + 7;
int m = group.size();
int dp[m + 1][n + 1][minProfit + 1];
memset(dp, 0, sizeof(dp));
dp[0][0][0] = 1; // 初始化
for (int i = 1; i <= m; i++) {
int grp = group[i - 1], pro = profit[i - 1];
for (int j = 0; j <= n; j++) { // 每个物品的代价
for (int k = 0; k <= minProfit; k++) { // 每个物品的价值
if (j < grp) dp[i][j][k] = dp[i - 1][j][k];
else dp[i][j][k] = (dp[i - 1][j][k] + dp[i - 1][j - grp][max(0, k - pro)]) % MOD;
}
}
}
int res = 0;
// 定义是刚好k个人，要把0-n的情况累加
for (int j = 0; j <= n; j++)
res = (res + dp[m][j][minProfit]) % MOD;
return res;
}可以状态压缩
int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
int MOD = 1e9 + 7;
int m = group.size();
int dp[n + 1][minProfit + 1];
memset(dp, 0, sizeof(dp));
dp[0][0] = 1; // 初始化
for (int i = 1; i <= m; i++) {
int grp = group[i - 1], pro = profit[i - 1];
for (int j = n; j >= grp; j--) {
for (int k = minProfit; k >= 0; k--) {
dp[j][k] = (dp[j][k] + dp[j - grp][max(0, k - pro)]) % MOD;
}
}
}
int res = 0;
// 定义是刚好k个人，要把0-n的情况累加
for (int j = 0; j <= n; j++)
res = (res + dp[j][minProfit]) % MOD;
return res;
}另一种定义
dp[i][j][k]：为考虑前 i 件物品，使用人数不超过 j，所得利润至少为 k 的方案数
int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
int MOD = 1e9 + 7;
int m = group.size();
int dp[m + 1][n + 1][minProfit + 1]; // 前面i件物品，至多j个人，利润至少为k的方案数
memset(dp, 0, sizeof(dp));
for (int j = 0; j <= n; j++) dp[0][j][0] = 1;
for (int i = 1; i <= m; i++) {
int grp = group[i - 1], pro = profit[i - 1];
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= minProfit; k++) {
if (j < grp) dp[i][j][k] = dp[i - 1][j][k];
else dp[i][j][k] = (dp[i - 1][j][k] + dp[i - 1][j - grp][max(0, k - pro)]) % MOD;
}
}
}
return dp[m][n][minProfit];
}可以状态压缩
int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
int MOD = 1e9 + 7;
int m = group.size();
int dp[n + 1][minProfit + 1];
memset(dp, 0, sizeof(dp));
for (int j = 0; j <= n; j++) dp[j][0] = 1; // 前面i件物品，至多j个人，利润至少为k的方案数
for (int i = 1; i <= m; i++) {
int grp = group[i - 1], pro = profit[i - 1];
for (int j = n; j >= grp; j--) {
for (int k = minProfit; k >= 0; k--) {
dp[j][k] = (dp[j][k] + dp[j - grp][max(0, k - pro)]) % MOD;
}
}
}
return dp[n][minProfit];
}
