मान लीजिए एक स्टोर है, बेचने के लिए कुछ आइटम हैं। प्रत्येक आइटम की कुछ कीमत है। हालांकि, कुछ विशेष ऑफर हैं, और एक विशेष ऑफर में एक या अधिक विभिन्न प्रकार के आइटम बिक्री मूल्य के साथ होते हैं। इसलिए हमारे पास कीमतों की सूची है, विशेष ऑफर का एक सेट, और प्रत्येक आइटम के लिए हमें जितनी संख्या में खरीदना है। कार्य यह है कि दी गई निश्चित आइटम के लिए हमें सबसे कम कीमत चुकानी होगी, जहां हम विशेष ऑफर का इष्टतम उपयोग कर सकते हैं।
यहां प्रत्येक विशेष ऑफर को एक सरणी के रूप में दर्शाया गया है, अंतिम संख्या इस विशेष ऑफर के लिए भुगतान की जाने वाली कीमत का प्रतिनिधित्व करती है, अन्य संख्याएं दर्शाती हैं कि यदि हम यह ऑफर खरीदते हैं तो हमें कितने विशिष्ट आइटम मिल सकते हैं।
उदाहरण के लिए, यदि इनपुट [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।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
memoनामक एक मैप परिभाषित करेंdirectPurchase()नामक एक विधि परिभाषित करें, यह कीमत और आवश्यकता सरणी लेता हैret := 0iको 0 से कीमत सरणी के आकार - 1 तक लूप करेंret := ret + price[i] * needs[i]
retलौटाएं- एक सहायक विधि परिभाषित करें। यह कीमत सरणी, विशेष ऑफर मैट्रिक्स, सरणी आवश्यकताएं और इंडेक्स लेगा:
- यदि
memo में needs हैतोmemo[needs]लौटाएं ret := directPurchase(price, need)iकोindexसे विशेष ऑफर मैट्रिक्स की पंक्तियों की संख्या - 1 तक लूप करें- यदि
, तोok := गलतसेट करें, और लूप से बाहर आएं need[j] - special[i, j]को अस्थायी सरणी में डालें
- यदि
- यदि
ok सही है, तोop1 := special[i] का अंतिम कॉलम तत्व + helper(price, special, temp, i)ret := 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]
आउटपुट
14