Skip to main content

879. Profitable Schemes

hard

Count the schemes (subsets of crimes) that hit a profit threshold using at most n criminals. Knapsack with two capacity dimensions — group[i] (members consumed) and a profit floor.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

There is a group of n members, and a list of various crimes they could commit. The ith crime generates a profit[i] and requires group[i] members to participate in it. If a member participates in one crime, that member can't participate in another crime. Let's call a profitable scheme any subset of these crimes that generates at least minProfit profit, and the total number of members participating in that subset of crimes is at most n. Return the number of schemes that can be chosen. Since the answer may be very large, return it modulo 10^9 + 7.

Constraints

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

Examples

Example 1

Input
n = 5, minProfit = 3, group = [2,2], profit = [2,3]
Output
2

Explanation: To make a profit of at least 3, the group could either commit crimes 0 and 1, or just crime 1. In total, there are 2 schemes.

Example 2

Input
n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
Output
7

Explanation: To make a profit of at least 5, the group could commit any crimes, as long as they commit one. There are 7 possible schemes: (0), (1), (2), (0,1), (0,2), (1,2), and (0,1,2).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Two-dimensional knapsack: capacity n (members) and a profit floor.

Hint 2

dp[i][j] = number of ways to use exactly i members and accumulate profit at least j after considering the processed crimes.

Hint 3

Iterate crimes. For each crime (g, p), update dp[i][j] += dp[i - g][max(0, j - p)] for valid i, j — sweep i from n down to g to avoid reusing the crime within an update.

Hint 4

Final answer: sum of dp[i][minProfit] for i in [0, n]. Apply mod 10^9 + 7.

Solution approach

Reveal approach

2D knapsack DP with a profit-floor dimension. dp[i][j] is the number of schemes using exactly i members with accumulated profit clipped at min(profit, minProfit) equal to j. Initialize dp[0][0] = 1. For each crime (g, p), update in-place: for i from n down to g and j from minProfit down to 0, dp[i][j] += dp[i - g][max(0, j - p)] mod 10^9 + 7. Profit beyond minProfit is clamped because we only care whether we cleared the threshold. After processing all crimes, the answer is sum of dp[i][minProfit] over i in 0..n. The 'clamp profit at minProfit' trick keeps the table size O(n * minProfit) instead of O(n * totalProfit).

Complexity

Time
O(C * n * minProfit)
Space
O(n * minProfit)

Related patterns

  • dynamic-programming
  • knapsack

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google

Practice these live with InterviewChamp.AI

Drill Profitable Schemes and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →