Profitable Schemes

Hard
891.

Profitable Schemes

Profitable Schemes is a hard coding problem on arrays and dynamic programming, asked in Amazon, Google and Adobe interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number} minProfit
 * @param {number[]} group
 * @param {number[]} profit
 * @return {number}
 */
var profitableSchemes = function(n, minProfit, group, profit) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Profitable Schemes — Solution in Python, Java & C++

Profitable Schemes solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Profitable Schemes is a hard coding problem on arrays and dynamic programming, asked in Amazon, Google and Adobe interviews.

  • Difficulty: Hard
  • Topics: Arrays, Dynamic Programming
  • Asked at: Amazon, Google, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Profitable Schemes

  1. Hint 1

    Two budgets: members used (a normal knapsack dimension) and profit earned.

  2. Hint 2

    Profit is a lower bound, not an exact target — so cap it at minProfit.

  3. Hint 3

    With the cap, dp[g][minProfit] means 'profit at least minProfit', which is exactly what is asked.

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]

Java

public static int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
    final int MOD = 1000000007;
    int[][] dp = new int[n + 1][minProfit + 1];
    for (int g = 0; g <= n; g++) dp[g][0] = 1;
    for (int i = 0; i < group.length; i++) {
        int gi = group[i], pi = profit[i];
        for (int g = n; g >= gi; g--) {
            for (int p = minProfit; p >= 0; p--) {
                int np = Math.max(0, p - pi);
                dp[g][p] = (dp[g][p] + dp[g - gi][np]) % MOD;
            }
        }
    }
    return dp[n][minProfit];
}

C++

int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
    const int MOD = 1000000007;
    vector<vector<int>> dp(n + 1, vector<int>(minProfit + 1, 0));
    for (int g = 0; g <= n; g++) dp[g][0] = 1;
    for (int i = 0; i < (int) group.size(); i++) {
        int gi = group[i], pi = profit[i];
        for (int g = n; g >= gi; g--) {
            for (int p = minProfit; p >= 0; p--) {
                int 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming