class Solution {
public:
int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
}
};
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) 。
提示：
1 <= n <= 1000 <= minProfit <= 1001 <= group.length <= 1001 <= group[i] <= 100profit.length == group.length0 <= profit[i] <= 100原站题解
cpp 解法, 执行用时: 88 ms, 内存消耗: 9.1 MB, 提交时间: 2023-09-21 23:32:40
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];
}
};
java 解法, 执行用时: 13 ms, 内存消耗: 39.2 MB, 提交时间: 2023-09-21 23:32:26
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];
}
}
javascript 解法, 执行用时: 128 ms, 内存消耗: 42.7 MB, 提交时间: 2023-09-21 23:32:06
/**
* @param {number} n
* @param {number} minProfit
* @param {number[]} group
* @param {number[]} profit
* @return {number}
*/
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];
};
golang 解法, 执行用时: 16 ms, 内存消耗: 3 MB, 提交时间: 2023-09-21 23:31:50
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
}
python3 解法, 执行用时: 1144 ms, 内存消耗: 16.5 MB, 提交时间: 2023-09-21 23:31:36
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]
python3 解法, 执行用时: 1632 ms, 内存消耗: 47.7 MB, 提交时间: 2023-09-21 23:31:02
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
javascript 解法, 执行用时: 240 ms, 内存消耗: 80.1 MB, 提交时间: 2023-09-21 23:30:49
/**
* @param {number} n
* @param {number} minProfit
* @param {number[]} group
* @param {number[]} profit
* @return {number}
*/
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;
};
golang 解法, 执行用时: 36 ms, 内存消耗: 21.1 MB, 提交时间: 2023-09-21 23:30:36
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
}
cpp 解法, 执行用时: 152 ms, 内存消耗: 53 MB, 提交时间: 2023-09-21 23:30:23
// dp[i][j][k] 表示在前 i 个工作中选择了 j 个员工，并且满足工作利润至少为 k 的情况下的盈利计划的总数目
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;
}
};
java 解法, 执行用时: 28 ms, 内存消耗: 50.2 MB, 提交时间: 2023-09-21 23:29:55
class Solution {
public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
int len = group.length, MOD = (int)1e9 + 7;
// dp[i][j][k] 表示在前 i 个工作中选择了 j 个员工，并且满足工作利润至少为 k 的情况下的盈利计划的总数目
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;
}
}