Profitable Schemes — Hard Problem & Solution

Problem statement

A gang of n members can commit crimes. Crime i needs group[i] members and earns profit[i]. A member who joins one crime cannot join another.

A profitable scheme is any subset of crimes using at most n members in total and earning at least minProfit. Return the number of such schemes, modulo 10^9 + 7.

Example 1

Input: n = 5, minProfit = 3, group = [2,2], profit = [2,3]
Output: 2
Explanation: Either crime 1 alone, or both together.

Example 2

Input: n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
Output: 7
Explanation: Any non-empty subset already clears the profit bar.

Example 3

Input: n = 1, minProfit = 1, group = [1], profit = [0]
Output: 0

Constraints

• 1 <= n <= 100
• 0 <= minProfit <= 100
• 1 <= group.length <= 100
• 1 <= group[i] <= 100
• profit.length == group.length
• 0 <= profit[i] <= 100

How to solve Profitable Schemes

A 0/1 knapsack in two dimensions, with the profit axis saturated. Since only 'at least minProfit' matters, any profit beyond it is indistinguishable — capping the index collapses the unbounded profit range to minProfit + 1 states.

Approach

1. dp[g][p] counts schemes using at most g members whose profit, capped at minProfit, is p.
2. Base: dp[g][0] = 1 for every g — the empty scheme.
3. For each crime, sweep g and p downwards (0/1 knapsack order) and add dp[g - group[i]][max(0, p - profit[i])].
4. The answer is dp[n][minProfit].

Why it works

Sweeping downwards ensures each crime is used at most once, as in the standard 0/1 knapsack. The max(0, p - profit[i]) is the saturation: reaching profit p from a state that already had enough profit is the same as reaching it from the capped state, so all of them merge into index minProfit without loss.

Complexity

• Time — O(len · n · minProfit)
• Space — O(n · minProfit)

Pitfalls

• Without capping the profit dimension, the state space is unbounded.
• Sweeping upwards turns it into an unbounded knapsack, letting a crime be committed twice.
• minProfit = 0 makes every subset valid, including the empty one.

Reference solution

Python

from typing import List

def profitableSchemes(n: int, minProfit: int, group: List[int], profit: List[int]) -> int:
    MOD = 1000000007
    dp = [[0] * (minProfit + 1) for _ in range(n + 1)]
    for g in range(n + 1):
        dp[g][0] = 1
    for gi, pi in zip(group, profit):
        for g in range(n, gi - 1, -1):
            for p in range(minProfit, -1, -1):
                np = max(0, p - pi)
                dp[g][p] = (dp[g][p] + dp[g - gi][np]) % MOD
    return dp[n][minProfit]

JavaScript

var profitableSchemes = function(n, minProfit, group, profit) {
    var MOD = 1000000007;
    var dp = [];
    for (var a = 0; a <= n; a++) {
        var row = [];
        for (var b = 0; b <= minProfit; b++) row.push(0);
        dp.push(row);
    }
    for (var g0 = 0; g0 <= n; g0++) dp[g0][0] = 1;
    for (var i = 0; i < group.length; i++) {
        var gi = group[i], pi = profit[i];
        for (var g = n; g >= gi; g--) {
            for (var p = minProfit; p >= 0; p--) {
                var np = Math.max(0, p - pi);
                dp[g][p] = (dp[g][p] + dp[g - gi][np]) % MOD;
            }
        }
    }
    return dp[n][minProfit];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Count Ways to Make Array With Product Hard
• The Number of Good Subsets Hard
• Number of Ways to Reorder Array to Get Same BST Hard
• Make Array Strictly Increasing Hard
• Odd Even Jump Hard
• Maximum Number of Events That Can Be Attended II Hard