C++ এ কেনাকাটার অফার

ধরুন একটা দোকান আছে, সেখানে কিছু জিনিস বিক্রি করার আছে। প্রতিটি জিনিসের কিছু দাম আছে। যাইহোক, কিছু বিশেষ অফার রয়েছে এবং একটি বিশেষ অফারে বিক্রয় মূল্য সহ এক বা একাধিক বিভিন্ন ধরণের আইটেম থাকে। তাই আমাদের কাছে দামের তালিকা, বিশেষ অফারগুলির একটি সেট এবং প্রতিটি আইটেমের জন্য আমাদের কেনার জন্য প্রয়োজনীয় সংখ্যা রয়েছে। কাজটি হল প্রদত্ত নির্দিষ্ট আইটেমের জন্য সর্বনিম্ন মূল্য খুঁজে বের করা, যেখানে আমরা বিশেষ অফারগুলির সর্বোত্তম ব্যবহার করতে পারি।

এখানে প্রতিটি বিশেষ অফারকে একটি অ্যারের আকারে উপস্থাপন করা হয়েছে, শেষ সংখ্যাটি এই বিশেষ অফারের জন্য আমাদের যে মূল্য দিতে হবে তা উপস্থাপন করে, অন্যান্য সংখ্যাগুলি প্রতিনিধিত্ব করে যে আমরা এই অফারটি কিনলে আমরা কতগুলি নির্দিষ্ট আইটেম পেতে পারি৷

সুতরাং ইনপুট যদি [2,5], [[3,0,5], [1,2,10]] এবং [3,2] এর মত হয়, তাহলে আউটপুট হবে 14। এর কারণ হল দুটি প্রকার আইটেম, A এবং B. তাদের দাম যথাক্রমে $2 এবং $5। বিশেষ অফার 1 এ, আমরা 3A এবং 0B এর জন্য $5 দিতে পারি। বিশেষ অফার 2-এ, আমরা 1A এবং 2B-এর জন্য $10 দিতে পারি। আমাদের 3A এবং 2B কিনতে হবে, তাই আমরা 1A এবং 2B (বিশেষ অফার 2) এর জন্য $10 এবং 2A এর জন্য $4 দিতে পারি৷

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

• মেমো নামে একটি মানচিত্র সংজ্ঞায়িত করুন

• directPurchase() নামে একটি পদ্ধতি সংজ্ঞায়িত করুন, এটি মূল্য নেয় এবং অ্যারে প্রয়োজন হয়

• ret :=0

• আমি 0 থেকে মূল্য বিন্যাসের আকার - 1

  এর মধ্যে

  • ret :=ret + মূল্য[i] * প্রয়োজন[i]

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

• একটি সহায়ক পদ্ধতি সংজ্ঞায়িত করুন। এটি মূল্য অ্যারে, বিশেষ অফার ম্যাট্রিক্স, অ্যারের চাহিদা এবং সূচক −

  নেবে

• যদি মেমোর প্রয়োজন থাকে তবে মেমো [needs]

  ফেরত দিন

• ret :=সরাসরি ক্রয় (মূল্য, প্রয়োজন)

• বিশেষ অফার ম্যাট্রিক্স - 1

  -এর সারিগুলির সংখ্যা থেকে পরিসীমা সূচকে i জন্য

  • যদি প্রয়োজন [j]

  • প্রয়োজন [j] - বিশেষ[i, j] টেম্প অ্যারেতে প্রবেশ করান

• যদি ঠিক হয়, তাহলে

  • op1 :=স্পেশাল[i] + হেল্পার (দাম, বিশেষ, টেম্প, i) এর শেষ কলাম উপাদান

  • ret :=সর্বনিম্ন ret এবং op1

• মেমো [প্রয়োজন] :=রিটার্ন এবং রিটার্ন

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• রিটার্ন হেল্পার(মূল্য, বিশেষ, চাহিদা, 0)

উদাহরণ (C++)

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   map <vector <int> , int> memo;
   int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
      return helper(price, special, needs, 0);
   }
   int helper(vector <int>& price, vector < vector <int> >& special, vector <int>& needs, int idx){
      if(memo.count(needs)) return memo[needs];
      int ret = directPurchase(price, needs);
      for(int i = idx; i < special.size(); i++){
         vector <int> temp;
         bool ok = true;
         for(int j = 0; j < special[i].size() - 1; j++){
            if(needs[j] < special[i][j]) {
               ok = false;
               break;
            }
            temp.push_back(needs[j] - special[i][j]);
         }
         if(ok){
            int op1 = special[i][special[i].size() - 1] + helper(price, special, temp, i);
            ret = min(ret, op1);
         }
      }
      return memo[needs] = ret;
   }
   int directPurchase(vector <int>& price, vector <int>& needs){
      int ret = 0;
      for(int i = 0; i < price.size(); i++){
         ret += price[i] * needs[i];
      }
      return ret;
   }
};
main(){
   vector<int> v1 = {2,5};
   vector<vector<int>> v2 = {{3,0,5},{1,2,10}};
   vector<int> v3 = {3,2};
   Solution ob;
   cout << (ob.shoppingOffers(v1, v2, v3));
}

ইনপুট

[2,5]
[[3,0,5],[1,2,10]]
[3,2]

আউটপুট

14