Profitable Schemes
Hard · dynamic programming
A crew of crew people can take on jobs. Job i needs people[i] people and pays pay[i]. Nobody can work on two jobs, so the jobs you choose must need at most crew people in total.
A plan is any set of jobs (possibly empty) whose total number of people is at most crew and whose total pay is at least min_pay. Two plans are different if they choose different sets of jobs, even when the jobs look alike.
Return the number of plans, modulo 10^9 + 7. If there are none, return 0.
Examples
Example 1
Input: crew = 3, min_pay = 3, people = [2, 2], pay = [2, 3]
Output: 1
Only the second job alone works. Both jobs together need 4 people, and the first job alone pays only 2.
Example 2
Input: crew = 5, min_pay = 3, people = [2, 2, 1], pay = [2, 3, 1]
Output: 5
The plans are jobs {1}, {0, 1}, {0, 2}, {1, 2} and {0, 1, 2}.
Example 3
Input: crew = 2, min_pay = 0, people = [1, 1], pay = [0, 0]
Output: 4
No pay is needed and both jobs fit, so all four sets of jobs, including the empty one, count.
Constraints
- 1 <= crew <= 60
- 0 <= min_pay <= 60
- 1 <= len(people) <= 60, and len(pay) == len(people).
- 1 <= people[i] <= 60
- 0 <= pay[i] <= 60