{x}
blog image

Profitable Schemes

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 109 + 7.

 

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).

 

Constraints:

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

Solution Explanation:

This problem asks to find the number of profitable schemes, which are subsets of crimes that meet two conditions: the total profit is at least minProfit, and the total number of members involved is at most n. The solution can be efficiently addressed using dynamic programming.

Approach 1: Recursion with Memoization (Top-Down DP)

This approach uses a recursive function dfs(i, j, k):

  • i: The index of the current crime being considered.
  • j: The number of members already used.
  • k: The current profit accumulated.

The base case is when all crimes are considered (i == len(group)). If the accumulated profit (k) is at least minProfit, a valid scheme is found (return 1); otherwise, it's not (return 0).

For each crime, we have two choices:

  1. Exclude the crime: Recursively call dfs(i + 1, j, k).
  2. Include the crime: If including the crime doesn't exceed the member limit (j + group[i] <= n), recursively call dfs(i + 1, j + group[i], min(k + profit[i], minProfit)). We use min(k + profit[i], minProfit) because exceeding minProfit doesn't improve the scheme's validity.

Memoization is crucial for efficiency. A 3D array f[i][j][k] stores the results of dfs(i, j, k), preventing redundant calculations.

Time Complexity: O(m * n * minProfit), where m is the number of crimes, n is the maximum number of members, and minProfit is the minimum required profit. Space Complexity: O(m * n * minProfit) due to the memoization array.

Approach 2: Dynamic Programming (Bottom-Up DP)

This approach uses a 3D DP array f[i][j][k]. f[i][j][k] stores the number of schemes using the first i crimes, at most j members, and at least k profit.

The base case is f[0][j][0] = 1 (no crimes, any number of members, profit 0).

The transition is:

  • f[i][j][k] = f[i-1][j][k] (exclude the i-th crime)
  • If j >= group[i-1], f[i][j][k] += f[i-1][j - group[i-1]][max(0, k - profit[i-1])] (include the i-th crime)

The final answer is f[m][n][minProfit].

Time Complexity: O(m * n * minProfit). Space Complexity: O(m * n * minProfit).

Code in Different Languages:

The code implementations for both approaches in Python, Java, C++, and Go are provided in the original response. They are organized in tabs and clearly show the implementation for each approach. Refer to the original response for the detailed code snippets. The code demonstrates both the top-down (memoization) and bottom-up dynamic programming solutions for this problem. Each implementation is designed to handle the constraints effectively and return the result modulo 109 + 7 to avoid potential integer overflow issues.