Profitable Crew Plans
Problem
A studio has crew people available and a list of possible projects. Project i needs group[i] people (who cannot work on anything else) and earns profit[i].
A plan is any subset of projects whose total headcount is at most crew and whose total profit is at least minProfit. Return the number of plans modulo 10^9 + 7. The empty subset counts if minProfit is 0.
Example 1
- Input:
- crew = 6, minProfit = 2, group = [1, 2, 4], profit = [0, 1, 2]
- Output:
- 3
{2} (4 people, profit 2), {0, 2} (5 people, profit 2) and {1, 2} (6 people, profit 3). {0, 1, 2} needs 7 people.
Example 2
- Input:
- crew = 5, minProfit = 4, group = [2, 3], profit = [2, 3]
- Output:
- 1
Only both projects together reach a profit of 4.
Constraints
- 1 ≤ crew ≤ 100
- 0 ≤ minProfit ≤ 100
- 1 ≤ group.length = profit.length ≤ 100
- 1 ≤ group[i] ≤ 100
- 0 ≤ profit[i] ≤ 100
Hint
Show the first hint
Each project is taken or not, and two quantities matter: people used and profit earned. That is a knapsack with two dimensions.
Walkthrough
How to approach it
01Clarify before coding
- Is the headcount limit 'at most crew'? Yes, so sum the counts over every m from 0 to crew at the end.
- Does the empty plan count? Only when minProfit is 0, since its profit is 0.
- Why modulo? The number of subsets can be up to 2^100.
02Brute force
Enumerate all 2^n subsets of projects and check people and profit for each.
Cost: O(2^n · n): impossible for n = 100.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.