Count Profitable Rollout Schemes
A team of engineers can each be assigned to at most one of several rollout tasks. Each task needs a fixed headcount and yields a fixed profit. Count how many subsets of tasks need at most G engineers total and yield at least P profit.
Problem
There are n tasks and g available engineers. Task i requires group[i] engineers and yields profit[i]. A scheme is a subset of tasks; an engineer can join at most one task in the scheme. A scheme is profitable if its total headcount <= g and its total profit >= minProfit. Return the number of profitable schemes modulo 1e9+7.
Input
Integers g and minProfit, and arrays group[] and profit[] of equal length n.
Output
An integer: the count of profitable schemes mod 1_000_000_007.
Constraints
- 1 <= n <= 100
- 0 <= g <= 100
- 0 <= minProfit <= 100
- 1 <= group[i] <= 100, 0 <= profit[i] <= 100
Examples
Example 1
Input
g = 5, minProfit = 3, group = [2,2], profit = [2,3]
Output
2
Schemes {task1} (profit 3) and {task0,task1} (profit 5) qualify.
Example 2
Input
g = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
Output
7
Seven subsets meet headcount <= 10 and profit >= 5.