# Leetcode-Profit Plan

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

n
Employees, they can complete a variety of jobs to create profits.

First

i
Kind of work will produce
profit[i]
Profit, it requires
group[i]
Members participate together. If a member is involved in one of these tasks, they cannot participate in the other.

Any work that produces at least

minProfit
The subset of profit is called the profit plan. And the total number of working members is at most
n
.

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 .

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

n
, And the lower limit of profit from work
minProfit
.

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 jobs$j$ employees, and the job profit is at least$k$The total number of profit plans in the case of . Hypothesis

group
The length of the array is
len
, Then without considering the modulo operation, the final answer is:

$\sum_{i=0}^{n}[len][i][minProfit]$

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:

$dp[i][j][k]=dp[i 1][j][k]$

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:

$dp[i][j][k]=dp[i 1][j][k]+dp[i 1][j-group[i]][\max(0,k profit[i] )]$

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