This is the 9th day I participated in the more text challenge. For details of the event, please see the more text challenge

## Title description

In the group

First

Any work that produces at least

How many plans are there to choose from? Because the answer is very large, the result modulus is returned$10^9 + 7$The value of$7$ .

**Example 1:**

Input: n = 5, minProfit = 3, group = [2,2], profit = [2,3] Output: 2 Explanation: To generate at least 3 profit, the group can complete work 0 and work 1, or only complete work 1. In general, there are two plans. Copy code

**Example 2:**

Input: n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8] Output: 7 Explanation: At least 5 profit is generated, as long as one of the tasks is completed, so the group can complete any task. There are 7 possible plans: (0), (1), (2), (0,1), (0,2), (1,2), and (0,1,2). Copy code

**prompt:**

- 1 $\le$ n$\le$ 100
- 0 $\le$ minProfit$\le$ 100
- 1 $\le$ group.length$\le$ 100
- 1 $\le$ group[i]$\le$ 100
- profit.length==group.length
- 0 $\le$ profit[i]$\le$ 100

## Problem-solving ideas

This question is very similar to the classic knapsack problem. The difference between the two is that the classic backpack problem has only one capacity limit, while this problem has two limits: the maximum number of employees in the group

Through the exercise of the classic knapsack problem, we know that the classic knapsack problem can be solved using two-dimensional dynamic programming: the two dimensions represent the restriction standards of items and capacity. For the above two limitations of this question, we can think of using three-dimensional dynamic programming to solve them. The three dimensions of the solution to this problem are: the currently selectable jobs, the number of selected group employees, and the lower limit of the current state of work profit.

According to the above analysis, we can define a three-dimensional array $dp$ the state of dynamic programming, where$dp[i][j][k]$ means first$i$selected from$i$ jobs$j$ employees, and the job profit is at least$k$The total number of profit plans in the case of$k$ . Hypothesis

So we can create a new three-dimensional array $dp[len+1][n+1][minProfit+1]$ , initialization$dp[0][0][0]=1$ . Next, analyze the state transition equation, for each job$i$ , we based on the current maximum number of employees$j$ . There are two situations where the current work can be carried out and the current work cannot be carried out:

If unable to carry out the current work $i$ , then obviously:

If you can carry out the current work $i$ , suppose the current group size is$group[i]$ , the work profit is$profit[i]$ , then without considering the modulus operation, there are:

Since the third dimension we define is that the working profit is at least $k$ instead of working profit happens to be$k$ , so the third dimension on the right side in the above state transition equation is$\max(0, k-\textit{profit}[i])$ instead of$k profit[i]$ .

## Code

```
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;
}
};
Copy code
```