# 879.profitable-schemes

## Statement

• Difficulty: Hard
• Tag: `数组` `动态规划`

``````输入：n = 5, minProfit = 3, group = [2,2], profit = [2,3]

``````输入：n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]

• `1 <= n <= 100`
• `0 <= minProfit <= 100`
• `1 <= group.length <= 100`
• `1 <= group[i] <= 100`
• `profit.length == group.length`
• `0 <= profit[i] <= 100`

• Difficulty: Hard
• Tag: `Array` `Dynamic Programming`

There is a group of `n` members, and a list of various crimes they could commit. The `ith` crime generates a `profit[i]` and requires `group[i]` members to participate in it. If a 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 `minProfit` profit, and the total number of members participating in that subset of crimes is at most `n`.

Return the number of schemes that can be chosen. Since the answer may be very large, return it modulo `109 + 7`.

Example 1:

``````Input: n = 5, minProfit = 3, group = [2,2], profit = [2,3]
Output: 2
Explanation: To make a profit of at least 3, the group could either commit crimes 0 and 1, or just crime 1.
In total, there are 2 schemes.``````

Example 2:

``````Input: n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
Output: 7
Explanation: To make a profit of at least 5, the group 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).``````

Constraints:

• `1 <= n <= 100`
• `0 <= minProfit <= 100`
• `1 <= group.length <= 100`
• `1 <= group[i] <= 100`
• `profit.length == group.length`
• `0 <= profit[i] <= 100`

## Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int mod = 1e9 + 7;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif

class Solution {
public:
int profitableSchemes(int n, int minProfit, vector<int> &group, vector<int> &profit) {
auto f = vector<vector<int>>(n + 1, vector<int>(minProfit + 5, 0));
f = 1;

int m = group.size();
for (int i = 0; i < m; i++) {
for (int j = n; j >= 0; j--) {
for (int k = minProfit; k >= 0; k--) {
int w = group[i];
int v = profit[i];
if (j + w <= n) {
int _j = j + w;
int _k = (k + v) >= minProfit ? minProfit : (k + v);
f[_j][_k] += f[j][k];
if (f[_j][_k] >= mod) {
f[_j][_k] -= mod;
}
}
}
}
}

int res = 0;
if (minProfit == 0) {
res += 1;
}

for (int i = 1; i <= n; i++) {
res += f[i][minProfit];
if (res >= mod) {
res -= mod;
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````