AlgoMaster Logo

Profitable Schemes

hardFrequencyUpdated September 21, 2026

Understanding the Problem

This problem is a variant of the 0/1 knapsack. A standard knapsack has one constraint (weight capacity) and maximizes value. Here there are two constraints: the number of members (at most n) and the profit (at least minProfit). Instead of maximizing anything, the task is to count the number of subsets that satisfy both constraints at once.

Each crime is a take-or-skip decision. Taking crime i uses group[i] members and adds profit[i]. The goal is to count how many subsets of crimes use at most n members in total while reaching at least minProfit profit.

The "at least minProfit" condition is the part that separates this from a plain knapsack. A typical knapsack tracks exact values. Here, any profit that meets or exceeds the threshold counts the same, so all profits >= minProfit can be treated as one equivalence class when counting.

Key Constraints:

  • 1 <= n <= 100 → The member count is small enough to use as a DP dimension.
  • 0 <= minProfit <= 100 → The profit threshold is small, so the profit dimension can be capped at minProfit (anything above it counts the same).
  • 1 <= group.length <= 100 → Up to 100 crimes, which is the "items" dimension of the knapsack.
  • 1 <= group[i] <= 100 and profit[i] >= 0 → Individual crime parameters are bounded and small.

With at most 100 crimes, 100 members, and a profit cap of 100, a three-dimensional state (crime index, members used, profit so far) has at most about 100 x 101 x 101 states, roughly one million. That is small enough for a polynomial DP, which rules out the exponential subset enumeration as a final answer.

Approach 1: Brute Force (Recursion)

Intuition

Try every possible subset of crimes. For each crime, either include it or skip it. After considering all crimes, check whether the total profit is at least minProfit and the total members used is at most n. If both hold, count that subset.

To keep the member constraint cheap, prune a branch the moment adding a crime would exceed n members, rather than checking only at the end. With up to 100 crimes there are 2^100 possible subsets, far too many to enumerate. This approach will not pass the time limit, but it establishes the correct logic that the later approaches optimize with memoization and then bottom-up DP.

Algorithm

  1. Use a recursive function count(index, members, profit) where index is the current crime, members is the number of members used so far, and profit is the total profit so far.
  2. Base case: if index == group.length, return 1 if profit >= minProfit, otherwise return 0.
  3. Skip the current crime: recurse with count(index + 1, members, profit).
  4. Take the current crime (only if members + group[index] <= n): recurse with count(index + 1, members + group[index], profit + profit[index]).
  5. Return the sum of both choices, modulo 10^9 + 7.

Visualization and Code

Loading animation...

The exponential branching repeats identical subproblems: different sequences of take/skip decisions can reach the same combination of crime index, members used, and profit accumulated. Caching the result for each distinct state collapses this repeated work.

Approach 2: Memoization (Top-Down DP)

Intuition

The brute force recursion explores the same state multiple times. If crimes 0 and 1 both use 2 members and each adds some profit, then taking crime 0 and skipping crime 1 can reach the same (index, members, profit) state as skipping crime 0 and taking crime 1. The subtree below that state is recomputed each time it is reached.

Memoization stores the result for each (index, members, profit) triple and returns the cached value on any later visit to the same state.

The profit dimension also needs capping. Since the only question is whether profit reaches minProfit, profit values of 5, 10, and 50 are indistinguishable when minProfit is 5. Capping profit at minProfit keeps the number of distinct states bounded and merges all "already satisfied" states into one.

Algorithm

  1. Create a 3D memo array of size m x (n+1) x (minProfit+1), initialized to -1.
  2. Use the same recursive logic as Approach 1, but before computing, check the memo. After computing, store the result.
  3. When tracking profit, use min(currProfit, minProfit) to cap it. This ensures the profit dimension stays within bounds.

Visualization and Code

Loading animation...

The memoization carries recursion overhead and a full 3D memo table. The bottom-up version drops the index dimension by processing crimes in a loop, leaving a 2D table over members and profit.

Approach 3: Bottom-Up DP (Optimized)

Intuition

Processing crimes one at a time in an outer loop removes the need to keep the crime index as a DP dimension. Only two dimensions remain: members used and profit so far.

Define dp[j][k] as the number of subsets of the crimes processed so far that use exactly j members and reach profit k (with k capped at minProfit). For each new crime, iterate j from n down to group[i]. The descending j is what keeps the same crime from being applied twice in one pass: each update reads dp[j - group[i]][k], a row that has not yet been touched for the current crime. The k loop also runs downward to 0.

Algorithm

  1. Create a 2D array dp[n+1][minProfit+1] initialized to 0. Set dp[0][0] = 1 (one way to use 0 members and earn 0 profit: take no crimes).
  2. For each crime i:
    • Iterate j from n down to group[i]. The descending order over members prevents the crime from being counted twice.
    • Iterate k from minProfit down to 0.
    • Compute newK = min(k + profit[i], minProfit).
    • Add dp[j - group[i]][k] to dp[j][newK], modulo 10^9 + 7.
  3. Sum dp[j][minProfit] for all j from 0 to n.

Visualization and Code

Loading animation...