DSA problem
Profitable Schemes
There is a group of n members, and a list of various crimes they could commit. The i-th crime generates a profit of profit[i] and requires group[i] members to participate in it. If a member participates in one crime, that member can't participate in another crime. Let's call a profitable scheme any subset of these crimes that generates at least minProfit profit, and the total number of members participating in that subset of crimes 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.
This is a 0/1 knapsack with two state dimensions and a counting objective. Each crime is an item that costs group[i] members and yields profit[i] profit; we want to count subsets where total member cost is at most n and total profit is at least minProfit. The challenge versus a vanilla knapsack is that we are counting schemes meeting a lower-bound on profit, not maximizing profit.
The key trick is to cap the profit dimension at minProfit. Any subset whose accumulated profit exceeds minProfit is no different from one that just hits minProfit — both qualify, and any further extra profit cannot disqualify a scheme. So we use dp[k][p] where k is members used (0 to n) and p is profit accumulated (0 to minProfit), with all profit beyond minProfit clamped to minProfit. dp[k][p] counts the number of subsets reaching this state.
The optimal solution is a 2D rolling DP: initialize dp[0][0] = 1 (the empty scheme) and for each crime (g, pr) iterate k from n down to g and p from minProfit down to 0, updating dp[k][p] += dp[k - g][max(0, p - pr)] modulo 10^9 + 7. The high-to-low iteration enforces the 0/1 (each crime used at most once) property. The answer is sum(dp[k][minProfit] for k in 0..n) modulo 10^9 + 7. Time is O(C * n * minProfit), space is O(n * minProfit).
Examples
n = 5, minProfit = 3, group = [2,2], profit = [2,3]2n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]7n = 1, minProfit = 1, group = [1,1,1], profit = [1,1,1]3Constraints
- 1 <= n <= 100
- 0 <= minProfit <= 100
- 1 <= group.length <= 100
- 1 <= group[i] <= 100
- profit.length == group.length and 0 <= profit[i] <= 100
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.