C++-এ শপিং অফার সমস্যা

একটি স্টোর আছে যেখানে কিছু আইটেম বিক্রি হয়। প্রতিটি আইটেমের দাম আছে। আবার কিছু স্পেশাল অফার আছে, যেখানে এক বা একাধিক আইটেম কম দামে পাওয়া যায়। আমাদের আইটেমের দামের তালিকা, স্পেশাল অফারগুলো, আর প্রতিটি আইটেম কতটুকু কিনতে হবে সেটি দেওয়া আছে। স্পেশাল অফারগুলো সর্বোচ্চ ব্যবহার করে ন্যূনতম খরচে ঠিক ঠিক দরকারি আইটেমগুলো কিনতে হবে।

প্রতিটি স্পেশাল অফার একটি অ্যারে আকারে দেওয়া থাকে: শেষ সংখ্যাটি হলো সেই অফারের দাম, বাকি সংখ্যাগুলো নির্দেশ করে কোন আইটেম কতটুকু मिलবে।

উদাহরণ: [2,5], [[3,0,5], [1,2,10]] এবং [3,2] হলে আউটপুট ১৪। কারণ দুটি আইটেম A আর B, দাম $2 আর $5। অফার ১: $5-এ 3A ও 0B। অফার ২: $10-এ 1A ও 2B। দরকার 3A ও 2B, তাই $10-এ অফার ২ নিলে 1A 2B পাওয়া যায়, বাকি 2A সাধারণ দামে $4-এ কিনলে মোট $14।

সমাধানের ধাপগুলো:

memo নামের একটি ম্যাপ সংজ্ঞায়িত করুন।
directPurchase() মেথড বানান যা price আর needs নেবে:
- ret := 0
- i = 0 থেকে price.size()-1 পর্যন্ত: ret := ret + price[i] * needs[i]
- ret ফেরত দিন।
helper মেথড বানান যা price, special, needs, index নেবে:
- যদি memo-এ needs থাকে, memo[needs] ফেরত দিন।
- ret := directPurchase(price, needs)
- i = index থেকে special.size()-1 পর্যন্ত:
  - ok := true
  - j = 0 থেকে special[i].size()-2 পর্যন্ত:
    - যদি needs[j] < special[i][j], ok := false, লুপ ব্রেক।
    - temp.push_back(needs[j] - special[i][j])
  - যদি ok true হয়:
    - op1 := special[i].back() + helper(price, special, temp, i)
    - ret := min(ret, op1)
- memo[needs] := ret ফেরত দিন।
মূল মেথড থেকে helper(price, special, needs, 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]