Profitable Schemes
Problem
There are n members and a list of crimes; crime i needs group[i] members and yields profit[i]. A group can do at most one crime each (a member used in one crime can't be in another). Count the schemes (subsets of crimes) that use at most n members total and earn at least minProfit, modulo 10⁹ + 7.
n = 5, minProfit = 3, group = [2,2], profit = [2,3]2def profitable_schemes(n, min_profit, group, profit):
MOD = 10 ** 9 + 7
dp = [[0] * (min_profit + 1) for _ in range(n + 1)]
for j in range(n + 1):
dp[j][0] = 1
for g, p in zip(group, profit):
for j in range(n, g - 1, -1):
for pr in range(min_profit, -1, -1):
dp[j][pr] = (dp[j][pr] + dp[j - g][max(0, pr - p)]) % MOD
return dp[n][min_profit]function profitableSchemes(n, minProfit, group, profit) {
const MOD = 1e9 + 7;
const dp = Array.from({ length: n + 1 }, () => new Array(minProfit + 1).fill(0));
for (let j = 0; j <= n; j++) dp[j][0] = 1;
for (let c = 0; c < group.length; c++) {
const g = group[c], p = profit[c];
for (let j = n; j >= g; j--)
for (let pr = minProfit; pr >= 0; pr--)
dp[j][pr] = (dp[j][pr] + dp[j - g][Math.max(0, pr - p)]) % MOD;
}
return dp[n][minProfit];
}int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
long MOD = 1_000_000_007L;
long[][] dp = new long[n + 1][minProfit + 1];
for (int j = 0; j <= n; j++) dp[j][0] = 1;
for (int c = 0; c < group.length; c++) {
int g = group[c], p = profit[c];
for (int j = n; j >= g; j--)
for (int pr = minProfit; pr >= 0; pr--)
dp[j][pr] = (dp[j][pr] + dp[j - g][Math.max(0, pr - p)]) % MOD;
}
return (int) dp[n][minProfit];
}int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
const long long MOD = 1e9 + 7;
vector<vector<long long>> dp(n + 1, vector<long long>(minProfit + 1, 0));
for (int j = 0; j <= n; j++) dp[j][0] = 1;
for (int c = 0; c < (int)group.size(); c++) {
int g = group[c], p = profit[c];
for (int j = n; j >= g; j--)
for (int pr = minProfit; pr >= 0; pr--)
dp[j][pr] = (dp[j][pr] + dp[j - g][max(0, pr - p)]) % MOD;
}
return dp[n][minProfit];
}Explanation
We want to count subsets of crimes that stay within a member budget and clear a minimum profit. This is a knapsack with two limits at once — members and profit — but instead of optimizing, we are tallying how many valid choices exist.
The table dp[j][pr] holds the number of schemes that use at most j members and reach profit "capped at" pr. The profit dimension is capped: any profit at or above minProfit is bucketed into the last column, since we only care about meeting the bar, not exceeding it.
The base case is dp[j][0] = 1 for every j: doing nothing is one valid scheme that meets a profit requirement of zero. Then for each crime needing g members and earning p, we add it in: dp[j][pr] += dp[j-g][max(0, pr-p)]. The max(0, ...) is what folds extra profit into the capped bucket.
We sweep j and pr downward so each crime is used at most once (the 0/1 knapsack trick), and every addition is taken modulo 10⁹ + 7.
Example: n = 5, minProfit = 3, group = [2,2], profit = [2,3]. The valid schemes are "crime 1 alone" (profit 3) and "both crimes" (profit 5, 4 members). So dp[5][3] = 2.