मान लीजिए G लोगों का एक गिरोह है और विभिन्न अपराधों की एक सूची है जो वे कर सकते हैं। i-वां अपराध profit[i] लाभ उत्पन्न करता है और group[i] गिरोह सदस्यों की भागीदारी की आवश्यकता होती है।
यदि एक गिरोह सदस्य एक अपराध में भाग ले रहा है, तो वह दूसरे अपराध में भाग नहीं ले सकता। अब आइए एक लाभदायक योजना को इन अपराधों के किसी भी उपसमुच्चय के रूप में परिभाषित करें जो कम से कम P लाभ उत्पन्न करता है, और उस उपसमुच्चय में भाग लेने वाले सदस्यों की कुल संख्या अधिकतम G है।
हमें ढूंढना है कि कितनी योजनाएं चुनी जा सकती हैं? उत्तर बहुत बड़ा हो सकता है, इसलिए मॉड्यूलो 10^9 + 7 में वापस करें।
उदाहरण के लिए, यदि G = 5, P = 3 और group = [2,2], profit = [2,3], तो आउटपुट 2 होगा।
हल करने का दृष्टिकोण
हम 2D डायनामिक प्रोग्रामिंग का उपयोग करते हैं:
dp[g][p] = g सदस्यों का उपयोग करके ठीक p लाभ (कम से कम p पर कैप्ड) प्राप्त करने के तरीकों की संख्या
dp[0][0] = 1 से इनिशियलाइज़ करें
प्रत्येक अपराध के लिए, dp को पीछे से अपडेट करें ताकि ओवरकाउंटिंग से बचा जा सके
संक्रमण: dp[g+group][min(P, p+profit)] += dp[g][p]
अंत में, सभी g <= G के लिए dp[g][P] का योग करें
उदाहरण
#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> &profit) {
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;
}
};
int main(){
Solution ob;
vector<int> v = {2,2}, v1 = {2,3};
cout << (ob.profitableSchemes(5,3,v, v1));
return 0;
}
इनपुट
5, 3, [2,2], [2,3]
आउटपुट
2
