Profitable Schemes
Problem (restated)
G crimes with group[i] members and profit[i]. At most n members total. Count schemes with profit ≥ minProfit (mod 10^9+7). Empty scheme has profit 0.
Intuition
0/1 knapsack: capacity members and capped profit (minProfit is enough). Count ways.
Approaches
2D knapsack (members × profit)
Tested onlyTime O(G·n·P)Space O(n·P)
Idea. dp[i][j] ways with i members and profit min(j, minProfit). Reverse iterate per crime. Sum dp[*][minProfit].
Walkthrough. n=5, minProfit=3, group=[2,2], profit=[2,3] → 2.
Trade-offs. Cap profit dimension at minProfit to keep state small.
Solution
export function profitableSchemes(
n: number,
minProfit: number,
group: number[],
profit: number[],
): number {
const MOD = 1_000_000_007;
const dp = Array.from({ length: n + 1 }, () => Array(minProfit + 1).fill(0));
dp[0]![0] = 1;
for (let k = 0; k < group.length; k++) {
const members = group[k]!, p = profit[k]!;
for (let i = n; i >= members; i--) {
for (let j = minProfit; j >= 0; j--) {
const nj = Math.min(minProfit, j + p);
dp[i]![nj] = (dp[i]![nj]! + dp[i - members]![j]!) % MOD;
}
}
}
let ans = 0;
for (let i = 0; i <= n; i++) ans = (ans + dp[i]![minProfit]!) % MOD;
return ans;
}
export function profitableSchemes(
n: number,
minProfit: number,
group: number[],
profit: number[],
): number {
const MOD = 1_000_000_007;
const dp = Array.from({ length: n + 1 }, () => Array(minProfit + 1).fill(0));
dp[0]![0] = 1;
for (let k = 0; k < group.length; k++) {
const members = group[k]!, p = profit[k]!;
for (let i = n; i >= members; i--) {
for (let j = minProfit; j >= 0; j--) {
const nj = Math.min(minProfit, j + p);
dp[i]![nj] = (dp[i]![nj]! + dp[i - members]![j]!) % MOD;
}
}
}
let ans = 0;
for (let i = 0; i <= n; i++) ans = (ans + dp[i]![minProfit]!) % MOD;
return ans;
}
Template connection
Multi-constraint 0/1 knapsack counting.
Reflection
- Which pattern gave this away within 90 seconds?
- What changed from the standard template?
- What would break the current solution?