Profitable Schemes
There is a group of n members, and a list of various crimes they could commit. The i^th crime generates profit[i] profit and requires group[i] members to participate in it. If a member participates in one crime, that member cannot participate in another crime.
A profitable scheme is any subset of these crimes that satisfies both conditions:
- The subset generates at least
minProfittotal profit. - The total number of members participating in the subset is at most
n.
Return the number of schemes that can be chosen. Since the answer may be very large, return it modulo 10^9 + 7.
Example 1
Input
n = 5, minProfit = 3, group = [2,2], profit = [2,3]Output
2To make a profit of at least 3, the group could either commit crimes 0 and 1, or just crime 1, so there are 2 schemes.
Example 2
Input
n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]Output
7To make a profit of at least 5, the group could commit any non-empty subset of crimes, giving 7 possible schemes.
Constraints
- 1 <= n <= 100
- 0 <= minProfit <= 100
- 1 <= group.length <= 100
- 1 <= group[i] <= 100
- profit.length == group.length
- 0 <= profit[i] <= 100