There are G people in a gang, and a list of various crimes they could commit.
The i-th crime generates a profit[i] and requires group[i] gang members to participate.
If a gang 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 P profit, and the total number of gang members participating in that subset of crimes is at most G.
How many schemes can be chosen? Since the answer may be very large, return it modulo 10^9 + 7.
Example 1:
Input: G = 5, P = 3, group = [2,2], profit = [2,3]
Output: 2
Explanation:
To make a profit of at least 3, the gang could either commit crimes 0 and 1, or just crime 1.
In total, there are 2 schemes.
Example 2:
Input: G = 10, P = 5, group = [2,3,5], profit = [6,7,8]
Output: 7
Explanation:
To make a profit of at least 5, the gang 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).
Note:
1 <= G <= 1000 <= P <= 1001 <= group[i] <= 1000 <= profit[i] <= 1001 <= group.length = profit.length <= 100
This problem is similar with the classic knapsack problem. Define dp[i][j] as the number of schemes that achieves profit i and use j gang members. j can go up to G as it does not make sense to compute schemes that use more than G people. What about profit i? It can go up to the sum of all profits, which can be 100 * 100 ~ O(10^4). However since the problem states a minimum profit P, we can just use dp[P][j] to represent the number of schemes with a >= P profit, whether it is exactly P or bigger than P does not matter as it already meet the threshold P. Using this observation, we can shrink the possible range i to be [0, P], which is O(100).
dp[0][0] = 1, there is 1 scheme that gives 0 profit and requires 0 member, that is the empty set.
for the kth crime, if we do not choose it, there is no impact on the final answer. If we choose it, we get extra profit[k] and group[k]. We can loop through all dp arrays and do the following update: dp[Math.min(i + profit[k], P)][j + group[k]] += dp[i][j], for all j that is <= G - group[k]. This means that if we already have dp[i][j] number of schemes to reach profit i and members j, then by picking one extra crime, we will have dp[i][j] more ways to reach profit Math.min(i + profit[k], P) and memeber j + group[k].
The implementation is pretty straightforward following the above analysis, or is it?
It turns out that the following transition from smaller states to bigger states is incorrect. It gives more ways than the right answer. Why is this? Consider example 1 given by the problem statement. When picking the 1st crime, we'll update dp[2][2] = 1; later we'll update add dp[2][2] of value 1 to dp[3][4], saying that we have 1 scheme to achieve profit >= 3 and using 4 members before we even consider the 2nd crime. But the 1st crime offers profit 2, requires 2 members, and each crime can only be picked once! The reason for this paradox is that when considering the same crime, we can not do a direct update on a bigger state. This update will be used again later to update an even bigger state. This counts as picking the same crime more than once. If we are allowed to pick the 1st crime twice, then we can of course 1 scheme to achieve profit >= 3 and using 4 members .
class Solution { public int profitableSchemes(int G, int P, int[] group, int[] profit) { int mod = (int)1e9 + 7, n = group.length; long[][] dp = new long[1 + P][1 + G]; dp[0][0] = 1; for(int i = 0; i < n; i++) { for(int j = 0; j <= P; j++) { for(int k = 0; k <= G; k++) { if(k <= G - group[i]) { int newP = Math.min(j + profit[i], P); int newG = k + group[i]; dp[newP][newG] = (dp[newP][newG] + dp[j][k]) % mod; } } } } long ans = 0; for(int j = 0; j <= G; j++) { ans = (ans + dp[P][j]) % mod; } return (int)ans; } }
How should we fix the above error?
Solution 1. Create 2 dp array, one for all states before a crime is picked; The other one for all states after a crime is picked.
Doing this ensures that we do not use "intermediate" states' changes to update even bigger states. We take a snapshot before choosing a crime, do all updates on this snapshot, then assign this newly updated snapshot of all states after picking a crime to dp.
class Solution { public int profitableSchemes(int G, int P, int[] group, int[] profit) { int mod = (int)1e9 + 7, n = group.length; long[][] dp = new long[1 + P][1 + G]; dp[0][0] = 1; for(int i = 0; i < n; i++) { long[][] next = new long[1 + P][]; for(int idx = 0; idx <= P; idx++) { next[idx] = Arrays.copyOf(dp[idx], 1 + G); } for(int j = 0; j <= P; j++) { for(int k = 0; k <= G - group[i]; k++) { int newP = Math.min(j + profit[i], P); int newG = k + group[i]; next[newP][newG] = (next[newP][newG] + dp[j][k]) % mod; } } dp = next; } long ans = 0; for(int j = 0; j <= G; j++) { ans = (ans + dp[P][j]) % mod; } return (int)ans; } }
Solution 2. When considering a crime, loop from bigger states to smaller states.
Using example 1 again, if we loop from "right to left", then we'll update dp[3][4] first when picking the 1st crime, dp[2][2] will be updated after dp[3][4] is done updating. This gives us the right result: dp[3][4] = 0, dp[2][2] = 1 when only considering the 1st crime of profit 2 and group member 2.
class Solution { public int profitableSchemes(int G, int P, int[] group, int[] profit) { int mod = (int)1e9 + 7, n = group.length; long[][] dp = new long[1 + P][1 + G]; dp[0][0] = 1; for(int i = 0; i < n; i++) { for(int j = P; j >= 0; j--) { for(int k = G - group[i]; k >= 0; k--) { int newP = Math.min(j + profit[i], P); int newG = k + group[i]; dp[newP][newG] = (dp[newP][newG] + dp[j][k]) % mod; } } } long ans = 0; for(int j = 0; j <= G; j++) { ans = (ans + dp[P][j]) % mod; } return (int)ans; } }