879. Profitable Schemes

Problem Description

In this LeetCode problem, we are given n, which represents the number of members in a group. We also have a list of crimes, where each crime can generate a certain amount of profit (profit[i]) and requires a specific number of group members (group[i]) to participate. The constraint is that a member cannot participate in more than one crime.

Our goal is to find the number of different "profitable schemes" we can form. A profitable scheme is defined as a subset of these crimes that yields at least a certain minProfit while utilizing n or fewer members in total.

We need to calculate the total number of such subsets of crimes that meet the criteria and return this number modulo 10^9 + 7 to avoid large output values.

Intuition

To tackle this problem, we can consider it as a variation of the classic 0/1 knapsack problem. The two constraints we are dealing with are the total number of members we have (n) and the minimum profit we aim to achieve (minProfit). The twist here is that, unlike the classic knapsack problem where we typically have only one constraint (weight), we have two constraints (group size and profit).

We can approach this problem with either recursion with memoization or dynamic programming. The basic intuition for both methods is to consider each crime and decide whether we include it in our scheme or not. We make this decision based on whether including the crime will keep the total number of participants within n and help us reach at least minProfit.

Recursion with Memoization:

We recursively try to build our solution by defining a function, say dfs(i, j, k), which tells us the number of schemes possible starting from the i-th job while having chosen j members and already accumulated a profit of k. We explore two possibilities at each step: including the current crime or excluding it. To prevent recalculations and improve efficiency, we use memoization to store intermediate results in a three-dimensional array.

Dynamic Programming:

Dynamic Programming (DP) offers a more systematic approach to this problem. Instead of recursively computing the answers, we iteratively build up a problem table f with dimensions representing the number of jobs considered so far, the number of employees used, and the current profit. The recurrence relation updates the table by considering the inclusion or exclusion of each job, much like the recursive approach, but done iteratively.

For the DP solution, we initialize our table with the understanding that, for zero jobs, we can only achieve zero profit with one scheme (doing nothing). We then iterate over each job and update the schemes count for various combinations of members used and profit gained, considering both options of including or excluding the crime.

Finally, whether we choose recursion with memoization or dynamic programming, the common intuition is to try each subset of crimes, enforce our constraints (not exceeding member limit and achieving at least minProfit), and count the number of valid schemes that arise from these choices.

Learn more about Dynamic Programming patterns.

Solution Approach

The problem has been approached with two algorithms: recursion with memoization and dynamic programming. Both methods aim to compute the number of ways in which crimes can be combined such that the total number of members used does not exceed n and the profit is at least minProfit. Here's how each approach works:

Recursion with Memoization:

The recursion with memoization approach uses a depth-first search (DFS) function named dfs(i, j, k) that represents number of schemes that can be formed starting from the i-th crime while having engaged j members and amassed a profit of k.

The base case of the recursion is when all crimes have been considered (i == n). If the accumulated profit k is greater than or equal to minProfit at this point, then we have found one valid scheme. If not, the scheme is invalid.

During the recursion, for each crime, we have the choice of either including it or not:

• If we choose not to include the crime, we simply move onto the next with dfs(i + 1, j, k).
• If we do include it and have enough members left (j + group[i] <= n), the profit increases by profit[i] (but not exceeding minProfit) and the number of members increases by group[i]. This gives us dfs(i + 1, j + group[i], min(k + profit[i], minProfit)).

Memoization is used to store these results in a three-dimensional array f[i][j][k] to ensure that each unique state is only computed once. This greatly reduces the number of redundant calculations, thus optimizing the function.

Dynamic Programming:

The dynamic programming approach involves iteratively filling out a three-dimensional array f[i][j][k], which holds similar meanings to the parameter of our dfs function. The dimensions i, j, and k respectively represent the number of jobs considered up to this point, the number of members involved, and the current accumulated profit.

Initialization is straightforward: f[0][j][0] = 1, signifying that having zero jobs only allows for a profit of 0, which has one trivial scheme (doing nothing).

From there, for each job i, we enumerate through all possible employee counts j and profit values k to update the DP table based on our choices:

• If job i is skipped, f[i][j][k] remains the same as f[i - 1][j][k].
• If job i is included, the count f[i][j][k] is increased by the count f[i - 1][j - group[i - 1]][max(0, k - profit[i - 1])]. This addition represents the schemes where job i contributes to the number of members and profit considering the constraints.

The answer to the problem would be the value of f[m][n][minProfit] after populating the table, as it represents the total number of schemes for m jobs with n members achieving at least minProfit.

Both the recursion with memoization and dynamic programming approaches provide a way to systematically traverse the search space of all possible crime scheme combinations, while ensuring the constraints are met, and efficiently count the number of valid schemes.

Example Walkthrough

Imagine a scenario where there are n = 2 members in a group and the given list of crimes with their respective profits and group requirements is as follows: profit = [1, 2] and group = [1, 2]. The minimum profit we want to achieve is minProfit = 2.

Let's walk through the dynamic programming approach to see how this problem can be solved.

Initially, we start by creating a 3D array f with dimensions [3][3][3] representing the number of jobs (including a 'zero' job), the number of members (0 through 2), and the profit values (0 through 2), respectively.

We know that no profit can be made without any jobs, so we initialize f[0][j][0] = 1 for 0 <= j <= n. This reflects the fact that there is one way to achieve zero profit with any number of available members by not committing any crimes.

Now, using the DP approach, we iteratively update the array f as follows:

1. Consider job 1 (crime 1 with profit 1 requiring 1 member): We look at combinations of employee counts and profits, and update the table by considering if we include job 1 or skip it.

   Including job 1 when we have 0 members already used and 0 profit so far would update f[1][1][1], indicating one scheme to achieve at least 1 profit with 1 member. Skipping job 1 would keep values same as previous, that is f[0][0][0] = 1.

2. Consider job 2 (crime 2 with profit 2 requiring 2 members): Now we proceed to update our array with the second job. This job requires both members to participate and yields the profit we want.

   If we include job 2 with 0 members and 0 profit used so far, we cannot do so because we don't have enough members (as it requires 2 and we only have 0). So, we skip to the entries where we have enough members.

   The entry f[2][2][2] is updated (now has value 1) representing one way to achieve a profit of 2 using both members by including the second job. Entries like f[2][1][1] remain as they were when derived from job 1, representing the available schemes to achieve profit 1 with 1 member, which cannot contribute to achieving profit 2 and so are not altered.

After populating our DP table, we look for f[NUM_JOBS][NUM_MEMBERS][minProfit] to find our answer. Here, f[2][2][2] represents the total number of schemes to achieve a profit of at least 2 while using up to 2 members, which is 1 (only by committing the second crime).

Therefore, the total number of profitable schemes for n=2, profit=[1,2], group=[1,2], and minProfit=2 is 1, indicating there is only one way to achieve the minimum profit without exceeding the number of group members. This solution counts all distinct arrangements that meet our criteria modulo 10^9 + 7.

Solution Implementation

Time and Space Complexity

The time complexity of the provided code is O(m * n * minProfit), where m represents the number of jobs, n represents the number of workers, and minProfit is the target minimum profit. This stems from the triple nested loops where the outermost loop runs for m jobs, the middle loop for n + 1 workers (from 0 to n), and the innermost loop for minProfit + 1 different profit targets (from 0 to minProfit).

The space complexity of the code is also O(m * n * minProfit). This is due to the 3-dimensional array f that is being created to store results for subproblems. The dimensions of this array are (m + 1) * (n + 1) * (minProfit + 1), corresponding to the number of jobs, workers plus one (to include the case of 0 workers), and minimum profit targets plus one (to include the case of 0 profit), respectively.

Learn more about how to find time and space complexity quickly using problem constraints.