## Algorithm

Problem Name: 879. Profitable Schemes

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 <= 100`
• `0 <= minProfit <= 100`
• `1 <= group.length <= 100`
• `1 <= group[i] <= 100`
• `profit.length == group.length`
• `0 <= profit[i] <= 100`

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const profitableSchemes = function(G, P, group, profit) {
const dp = Array.from({ length: P + 1 }, () => new Array(G + 1).fill(0))
dp[0][0] = 1
let res = 0,
mod = 10 ** 9 + 7
for (let k = 0; k  <  group.length; k++) {
let g = group[k],
p = profit[k]
for (let i = P; i >= 0; i--)
for (let j = G - g; j >= 0; j--)
dp[Math.min(i + p, P)][j + g] =
(dp[Math.min(i + p, P)][j + g] + dp[i][j]) % mod
}
for (let x of dp[P]) res = (res + x) % mod
return res
}
``````
Copy The Code &

Input

cmd
n = 5, minProfit = 3, group = [2,2], profit = [2,3]

Output

cmd
2

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def profitableSchemes(self, G: int, P: int, group: List[int], profit: List[int]) -> int:
dp = [[0] * (G + 1) for i in range(P + 1)]
dp[0][0] = 1
for p, g in zip(profit, group):
for i in range(P, -1, -1):
for j in range(G - g, -1, -1):
dp[min(i + p, P)][j + g] += dp[i][j]
return sum(dp[P]) % (10**9 + 7)
``````
Copy The Code &

Input

cmd
n = 5, minProfit = 3, group = [2,2], profit = [2,3]

Output

cmd
2