Welcome to Subscribe On Youtube
879. Profitable Schemes
Description
There is a group of n
members, and a list of various crimes they could commit. The i^{th}
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 10^{9} + 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 <= 100
0 <= minProfit <= 100
1 <= group.length <= 100
1 <= group[i] <= 100
profit.length == group.length
0 <= profit[i] <= 100
Solutions
Solution 1: recursion with memoization
We design a function $dfs(i, j, k)$, which means that we start from the $i$th job, and have chosen $j$ employees, and the current profit is $k$, then the number of schemes in this case is $dfs(0, 0, 0)$.
The execution process of function $dfs(i, j, k)$ is as follows:
 If $i = n$, it means that all the jobs have been considered. If $k \geq minProfit$, the number of schemes is $1$, otherwise the number of schemes is $0$;
 If $i < n$, we can choose not to choose the $i$th job, then the number of schemes is $dfs(i + 1, j, k)$; if $j + group[i] \leq n$, we can also choose the $i$th job, then the number of schemes is $dfs(i + 1, j + group[i], \min(k + profit[i], minProfit))$. Here we limit the profit upper limit to $minProfit$, because the profit exceeding $minProfit$ has no effect on our answer.
Finally, return $dfs(0, 0, 0)$.
In order to avoid repeated calculation, we can use the method of memoization. We use a threedimensional array $f$ to record all the results of $dfs(i, j, k)$. When we calculate the value of $dfs(i, j, k)$, we store it in $f[i][j][k]$. When we call $dfs(i, j, k)$, if $f[i][j][k]$ has been calculated, we return $f[i][j][k]$ directly.
The time complexity is $O(m \times n \times minProfit)$, and th e space complexity is $O(m \times n \times minProfit)$. Here $m$ and $n$ are the number of jobs and employees, and $minProfit$ is the minimum profit.
Solution 2: Dynamic Programming
We define $f[i][j][k]$ to be the number of schemes to make a profit of at least $k$ with $i$ jobs and $j$ workers. Initially, we have $f[0][j][0] = 1$, which means that there is only one scheme to make a profit of $0$ without any jobs.
For the $i$th job, we can choose to work or not to work. If we do not work, then $f[i][j][k] = f[i  1][j][k]$; if we work, then $f[i][j][k] = f[i  1][j  group[i  1]][max(0, k  profit[i  1])]$. We need to enumerate $j$ and $k$, and add up all the schemes.
The final answer is $f[m][n][minProfit]$.
The time complexity is $O(m \times n \times minProfit)$, and the space complexity is $O(m \times n \times minProfit)$. Here $m$ and $n$ are the numbers of jobs and workers, and $minProfit$ is the minimum profit to make.

class Solution { public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) { final int mod = (int) 1e9 + 7; int m = group.length; int[][][] f = new int[m + 1][n + 1][minProfit + 1]; for (int j = 0; j <= n; ++j) { f[0][j][0] = 1; } for (int i = 1; i <= m; ++i) { for (int j = 0; j <= n; ++j) { for (int k = 0; k <= minProfit; ++k) { f[i][j][k] = f[i  1][j][k]; if (j >= group[i  1]) { f[i][j][k] = (f[i][j][k] + f[i  1][j  group[i  1]][Math.max(0, k  profit[i  1])]) % mod; } } } } return f[m][n][minProfit]; } }

class Solution { public: int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) { int m = group.size(); int f[m + 1][n + 1][minProfit + 1]; memset(f, 0, sizeof(f)); for (int j = 0; j <= n; ++j) { f[0][j][0] = 1; } const int mod = 1e9 + 7; for (int i = 1; i <= m; ++i) { for (int j = 0; j <= n; ++j) { for (int k = 0; k <= minProfit; ++k) { f[i][j][k] = f[i  1][j][k]; if (j >= group[i  1]) { f[i][j][k] = (f[i][j][k] + f[i  1][j  group[i  1]][max(0, k  profit[i  1])]) % mod; } } } } return f[m][n][minProfit]; } };

class Solution: def profitableSchemes( self, n: int, minProfit: int, group: List[int], profit: List[int] ) > int: mod = 10**9 + 7 m = len(group) f = [[[0] * (minProfit + 1) for _ in range(n + 1)] for _ in range(m + 1)] for j in range(n + 1): f[0][j][0] = 1 for i, (x, p) in enumerate(zip(group, profit), 1): for j in range(n + 1): for k in range(minProfit + 1): f[i][j][k] = f[i  1][j][k] if j >= x: f[i][j][k] = (f[i][j][k] + f[i  1][j  x][max(0, k  p)]) % mod return f[m][n][minProfit]

func profitableSchemes(n int, minProfit int, group []int, profit []int) int { m := len(group) f := make([][][]int, m+1) for i := range f { f[i] = make([][]int, n+1) for j := range f[i] { f[i][j] = make([]int, minProfit+1) } } for j := 0; j <= n; j++ { f[0][j][0] = 1 } const mod = 1e9 + 7 for i := 1; i <= m; i++ { for j := 0; j <= n; j++ { for k := 0; k <= minProfit; k++ { f[i][j][k] = f[i1][j][k] if j >= group[i1] { f[i][j][k] += f[i1][jgroup[i1]][max(0, kprofit[i1])] f[i][j][k] %= mod } } } } return f[m][n][minProfit] }