Skip to main content

879. Profitable Schemes

hard

Count subsets of crimes whose total members fit a cap and whose total profit meets a minimum. A two-dimensional knapsack capped from above on profit.

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 0/1 knapsack. dp[m][p] = schemes using m members with profit exactly p.

Hint 2

Cap profit from above: any p >= minProfit collapses into the single bucket minProfit.

Hint 3

Iterate crimes outer, reverse-iterate members and profit-buckets inner for 0/1 semantics.

Solution approach

Reveal approach

Two-dimensional 0/1 knapsack with a clever profit cap. Define dp[m][p] as the number of schemes using exactly m members with profit exactly p — but cap p at minProfit by collapsing every p >= minProfit into the single bucket minProfit. This caps the second dimension. Initialize dp[0][0] = 1. For each crime (g, profit_i), iterate m from n down to g and p from minProfit down to 0: dp[m][min(minProfit, p + profit_i)] += dp[m - g][p], modulo 10^9 + 7. The reverse iteration enforces 0/1 (each crime used at most once). After processing every crime, sum dp[m][minProfit] across all m from 0 to n and return the total. O(L * n * minProfit) time where L is the crime count.

Complexity

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

Related patterns

  • dynamic-programming
  • knapsack-0-1

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 DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →