資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++ 盈利方案
假設有一個由 G 個人組成的團伙，以及他們可以實施的各種犯罪行為的列表。第 i 個犯罪行為會產生利潤值 profit[i]，並且需要 group[i] 個團伙成員參與。
如果一個團伙成員參與了一項犯罪行為，那麼他不能參與另一項犯罪行為。現在我們定義盈利方案為這些犯罪行為的任何子集，該子集產生的利潤至少為 P，並且參與該子集犯罪行為的成員總數最多為 G。
我們必須找到可以選擇的方案數量？答案可能非常大，因此返回它模 10^9 + 7。
因此，如果輸入類似於 G = 5，P = 3，group = [2,2]，profit = [2,3]，則輸出將為 2
為了解決這個問題，我們將遵循以下步驟：
ret := 0
定義一個大小為 (G + 1) x (P + 1) 的二維陣列 dp
dp[0, 0] := 1
初始化 k := 0，當 k < group 的大小，更新 (k 增加 1)，執行：
p := profit[k]，g := group[k]
初始化 i := G - g，當 i >= 0，更新 (i 減少 1)，執行：
初始化 j := P，當 j >= 0，更新 (j 減少 1)，執行：
dp[i + g, min(P, j + p)]
dp[i + g, min(P, j + p)]
初始化 i := 0，當 i <= G，更新 (i 增加 1)，執行：
ret := ret + dp[i, P]
ret := ret mod m
返回 ret
讓我們看看下面的實現以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7;
class Solution {
public:
int profitableSchemes(int G, int P, vector<int> &group, vector<int> &lprofit) {
int ret = 0;
vector<vector<int>> dp(G + 1, vector<int>(P + 1));
dp[0][0] = 1;
for (int k = 0; k < group.size(); k++) {
int p = profit[k];
int g = group[k];
for (int i = G - g; i >= 0; i--) {
for (int j = P; j >= 0; j--) {
dp[i + g][min(P, j + p)] += dp[i][j];
dp[i + g][min(P, j + p)] %= m;
}
}
}
for (int i = 0; i <= G; i++) {
ret += dp[i][P];
ret %= m;
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {2,2}, v1 = {2,3};
cout << (ob.profitableSchemes(5,3,v, v1));
}輸入
5, 3, [2,2], [2,3]
輸出
2
更新於：2020年6月4日
瀏覽量：158
廣告