Profitable Schemes

Profitable Schemes

What is this problem about?

The Profitable Schemes problem gives you a list of criminal schemes, each requiring some members and generating some profit. Find how many subsets of schemes generate at least minProfit using at most n gang members. Return the count modulo 10^9+7. This hard coding problem is a 2D knapsack: limited capacity (members) and minimum requirement (profit). The array and dynamic programming interview pattern is fully tested.

Why is this asked in interviews?

Amazon and Google ask this because it extends the standard 0/1 knapsack to two constraints: capacity (members ≤ n) and floor constraint (profit ≥ minProfit). The "at least" constraint for profit requires careful DP state design.

Algorithmic pattern used

2D DP (members, profit). dp[j][p] = number of schemes using exactly j members with exactly p profit (or profit capped at minProfit). For each scheme (members, profit): update DP in reverse: dp[j][p] += dp[j-members][max(0,p-profit)]. Answer = sum of dp[j][minProfit] for j=0..n. The profit dimension is capped at minProfit (any profit above minimum counts the same).

Example explanation

n=5, minProfit=3, group=[2,2], profit=[2,3].

• Scheme 0: 2 members, 2 profit.
• Scheme 1: 2 members, 3 profit. Valid subsets: {scheme1} = 1 way (2 members, 3 profit ≥ 3). {scheme0,scheme1} = 4 members, 5 profit ≥ 3 ✓. Others give profit < 3. Count = 2.

Common mistakes candidates make

• Not capping profit at minProfit (causing wrong transitions for "at least minProfit" states).
• Forward DP update (allows same scheme multiple times — must be reverse for 0/1 knapsack).
• Not initializing dp[0][0]=1 (one way to use 0 members with 0 profit: select nothing).
• Off-by-one: profit capping uses min(p, minProfit).

Interview preparation tip

Profitable Schemes is 2D 0/1 knapsack with a floor constraint. The key insight: cap the profit dimension at minProfit because any profit above the minimum is treated the same (we only care about reaching the threshold, not exceeding it). Practice: "0/1 knapsack with budget and minimum profit," "task scheduling with two resources," "item selection with two constraints." The profit-capping technique generalizes to any "at least k" DP constraint.