Leetcode-Profit Plan

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 returned109+710^9 + 7The 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 dpdp the state of dynamic programming, wheredp[i][j][k]dp[i][j][k] means firstiiselected from jobsjj employees, and the job profit is at leastkkThe 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:

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

So we can create a new three-dimensional array dp[len+1][n+1][minProfit+1]dp[len+1][n+1][minProfit+1] , initializationdp[0][0][0]=1dp[0][0][0]=1 . Next, analyze the state transition equation, for each jobii , we based on the current maximum number of employeesjj . 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 ii , then obviously:

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

If you can carry out the current work ii , suppose the current group size isgroup[i]group[i] , the work profit isprofit[i]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])]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 kk instead of working profit happens to bekk , so the third dimension on the right side in the above state transition equation ismax (0,k profit[i])\max(0, k-\textit{profit}[i]) instead ofk profit[i]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