数据结构
网络
关系数据库管理系统 (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
广告