C++-এ প্রফিটেবল স্কিমের সংখ্যা

সমস্যা বিবরণ

G সদস্যের গ্যাং এবং কিছু অপরাধের তালিকা দেওয়া থাকলে। i-তম অপরাধে profit[i] লাভ এবং group[i] সদস্য লাগে। একটি সদস্য একাধিক অপরাধে যোগ দিতে পারবে না। কমপক্ষে P লাভ এবং সর্বোচ্চ G সদস্য ব্যবহার করে কতগুলো স্কিম বানানো যায় (মডুলো 10^9+7)?

উদাহরণ

G = 5, P = 3, group = [2,2], profit = [2,3] → আউটপুট = 2

সমাধান পদ্ধতি

• DP[i][j] = i সদস্য ব্যবহার করে j লাভ অর্জনের স্কিম সংখ্যা।
• প্রতিটি অপরাধের জন্য রিভার্স লুপে DP আপডেট করা হয়।
• লাভ P-এর বেশি হলে P-এ ক্যাপ করা হয়।
• শেষে সব i-এর জন্য dp[i][P] যোগ করা হয়।

C++ বাস্তবায়ন

#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) {
        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], 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;
                }
            }
        }
        
        int ret = 0;
        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