Problem
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 <= 100
0 <= P <= 100
1 <= group[i] <= 100
0 <= profit[i] <= 100
1 <= group.length = profit.length <= 100
Solution: DP
Time complexity: O(KPG)
Space complexity: O(KPG)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua // Running time: 64 ms class Solution { public: int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) { const int kMod = 1000000007; const int K = group.size(); // dp[k][i][j]:= # of schemes of making profit i with j people by commiting first k crimes. vector<vector<vector<int>>> dp(K + 1, vector<vector<int>>(P + 1, vector<int>(G + 1, 0))); dp[0][0][0] = 1; for (int k = 1; k <= K; ++k) { const int p = profit[k - 1]; const int g = group[k - 1]; for (int i = 0; i <= P; ++i) for (int j = 0; j <= G; ++j) dp[k][i][j] = (dp[k - 1][i][j] + (j < g ? 0 : dp[k - 1][max(0, i - p)][j - g])) % kMod; } return accumulate(begin(dp[K][P]), end(dp[K][P]), 0LL) % kMod; } }; |
Space complexity: O(PG)
v1: Dimension reduction by copying.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua // Running time: 24 ms class Solution { public: int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) { const int kMod = 1000000007; const int K = group.size(); // dp[i][j]:= # of schemes of making profit i with j people. vector<vector<int>> dp(P + 1, vector<int>(G + 1, 0)); dp[0][0] = 1; for (int k = 1; k <= K; ++k) { auto tmp = dp; const int p = profit[k - 1]; const int g = group[k - 1]; for (int i = 0; i <= P; ++i) for (int j = 0; j <= G; ++j) tmp[i][j] = (tmp[i][j] + (j < g ? 0 : dp[max(0, i - p)][j - g])) % kMod; dp.swap(tmp); } return accumulate(begin(dp[P]), end(dp[P]), 0LL) % kMod; } }; |
v2: Dimension reduction by using rolling array.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
// Author: Huahua // Running time: 16 ms class Solution { public: int profitableSchemes(int G, int P, vector<int>& group, vector<int>& profit) { const int kMod = 1000000007; // dp[i][j]:= # of schemes of making profit i with j people. vector<vector<int>> dp(P + 1, vector<int>(G + 1, 0)); dp[0][0] = 1; const int K = group.size(); for (int k = 0; k < K; ++k) { const int p = profit[k]; const int g = group[k]; for (int i = P; i >= 0; --i) { const int ip = min(P, i + p); for (int j = G - g; j >= 0; --j) dp[ip][j + g] = (dp[ip][j + g] + dp[i][j]) % kMod; } } return accumulate(begin(dp[P]), end(dp[P]), 0LL) % kMod; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment