C++ এ লাভজনক স্কিম

ধরুন G লোকদের সাথে একটি গ্যাং আছে এবং তারা যে বিভিন্ন অপরাধ করতে পারে তার একটি তালিকা। i-th অপরাধ একটি মুনাফা মূল্যের মুনাফা তৈরি করে[i] এবং গ্রুপ[i] গ্যাং সদস্যদের অংশগ্রহণের প্রয়োজন হয়৷

যদি একজন গ্যাং সদস্য একটি অপরাধে অংশগ্রহণ করে, তাহলে সে অন্য অপরাধে অংশগ্রহণ করতে পারবে না। এখন আসুন লাভজনক স্কিম সংজ্ঞায়িত করা যাক এই অপরাধগুলির যে কোনও উপসেট যা কমপক্ষে P মুনাফা তৈরি করে, এবং অপরাধের সেই উপসেটে অংশগ্রহণকারী মোট সদস্য সংখ্যা সর্বাধিক G৷

আমাদের খুঁজে বের করতে হবে কয়টি স্কিম বেছে নেওয়া যায়? উত্তরটি অনেক বড় হতে পারে, তাই এটি মডিউল 10^9 + 7 ফেরত দিন।

সুতরাং, যদি ইনপুট হয় G =5, P =3 এবং গ্রুপ =[2,2], লাভ =[2,3], তাহলে আউটপুট হবে 2

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• ret :=0

• আকারের একটি 2D অ্যারে dp সংজ্ঞায়িত করুন (G + 1) x (P + 1)

• dp[0, 0] :=1

• আরম্ভ করার জন্য k :=0, যখন k <গোষ্ঠীর আকার, আপডেট (k 1 দ্বারা বৃদ্ধি), −

  • p :=লাভ[k], g :=গ্রুপ[k]

  • আরম্ভ করার জন্য i :=G - g, যখন i>=0, আপডেট করুন (i 1 দ্বারা কম করুন), −

    • j শুরু করার জন্য :=P, যখন j>=0, আপডেট করুন (j 1 দ্বারা কম করুন), do−

      • dp[i + g, সর্বনিম্ন P এবং j + p]

      • dp[i + g, সর্বনিম্ন P এবং j + p]

• আরম্ভ করার জন্য i :=0, যখন i <=G, আপডেট করুন (i 1 দ্বারা বাড়ান), করবেন −

  • ret :=ret + dp[i, P]

  • ret :=ret mod m

• রিটার্ন রিটার্ন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#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