Profitable Schemes
Hard · Dynamic Programming · Array · Dynamic Programming
Problem
A gang has n members and a list of possible crimes. Crime i needs exactly group[i] members and earns profit[i]. A member who takes part in one crime cannot take part in another.
A profitable scheme is any subset of the crimes whose total profit is at least minProfit and whose total number of members is at most n.
Return the number of profitable schemes, modulo 10^9 + 7. When minProfit is 0, the empty subset counts as a scheme.
Examples
Input: n = 4, minProfit = 2, group = [2,3,1], profit = [1,2,1] Output: 3
The valid schemes are {1}, {0, 2} and {1, 2}; every other subset earns too little or needs more than 4 members.
Input: n = 2, minProfit = 0, group = [1,1], profit = [0,5] Output: 4
Any profit qualifies, and all four subsets, the empty one included, need at most 2 members.
Input: n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8] Output: 7
Every non-empty subset earns at least 6, and all of them fit in 10 members: 7 schemes.
Constraints
- 1 <= n <= 100
- 0 <= minProfit <= 100
- 1 <= len(group) <= 100
- len(profit) == len(group)
- 1 <= group[i] <= 100
- 0 <= profit[i] <= 100
Approaches
- Baseline: track exact total profit — time O(c · n · S), space O(n · S)
Follow-up
Can you use a single table and still use each crime once? Yes: sweep members downward, as above. The use cases drop the member limit (count subsets with sum at least a target) and turn counting into minimizing (fewest members that reach the profit).
Related problems
Start free on Cariara · Coding problems · System design studio
