मान लीजिए कोई दुकान है, बेचने के लिए कुछ सामान हैं। प्रत्येक वस्तु की कुछ कीमत होती है। हालांकि, कुछ विशेष ऑफ़र हैं, और एक विशेष ऑफ़र में बिक्री मूल्य के साथ एक या अधिक विभिन्न प्रकार के आइटम होते हैं। इसलिए हमारे पास कीमतों की सूची है, विशेष ऑफ़र का एक सेट है, और वह संख्या है जो हमें प्रत्येक आइटम के लिए खरीदने की आवश्यकता है। कार्य यह है कि हमें दिए गए कुछ निश्चित वस्तुओं के लिए न्यूनतम कीमत का भुगतान करना है, जहां हम विशेष प्रस्तावों का इष्टतम उपयोग कर सकते हैं।
यहां प्रत्येक विशेष ऑफ़र को एक सरणी के रूप में दर्शाया जाता है, अंतिम संख्या उस कीमत का प्रतिनिधित्व करती है जिसे हमें इस विशेष ऑफ़र के लिए भुगतान करने की आवश्यकता होती है, अन्य संख्याएं दर्शाती हैं कि यदि हम इस ऑफ़र को खरीदते हैं तो हमें कितने विशिष्ट आइटम मिल सकते हैं।
तो अगर इनपुट [2,5], [[3,0,5], [1,2,10]] और [3,2] जैसा है, तो आउटपुट 14 होगा। ऐसा इसलिए है क्योंकि दो प्रकार हैं वस्तुओं की, ए और बी। उनकी कीमतें क्रमशः $ 2 और $ 5 हैं। विशेष ऑफर 1 में, हम 3A और 0B के लिए $5 का भुगतान कर सकते हैं। विशेष ऑफ़र 2 में, हम 1A और 2B के लिए $10 का भुगतान कर सकते हैं। हमें 3ए और 2बी खरीदना है, इसलिए हम 1ए और 2बी के लिए $10 और 2ए के लिए $4 का भुगतान कर सकते हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
मेमो नामक मानचित्र परिभाषित करें
-
DirectPurchase () नामक एक विधि को परिभाषित करें, यह मूल्य लेता है और सरणियों की आवश्यकता होती है
-
रिट:=0
-
मेरे लिए 0 से लेकर मूल्य सरणी के आकार तक - 1
-
रिट :=रिट + कीमत[i] * जरूरतें[i]
-
-
वापसी रिट
-
एक सहायक विधि को परिभाषित कीजिए। यह मूल्य सरणी, विशेष ऑफ़र मैट्रिक्स, सरणी की ज़रूरतें और अनुक्रमणिका लेगा -
-
अगर मेमो की जरूरत है तो मेमो लौटाएं[जरूरतें]
-
ret :=DirectPurchase(कीमत, ज़रूरत)
-
i के लिए श्रेणी अनुक्रमणिका से लेकर विशेष ऑफ़र मैट्रिक्स की पंक्तियों की संख्या - 1
-
अगर जरूरत है [j] <विशेष [i, j], तो ठीक सेट करें:=गलत, और लूप से बाहर आएं
-
जरूरत डालें [j] - विशेष [i, j] अस्थायी सरणी में
-
-
अगर ठीक है तो सच है, तब
-
op1:=विशेष का अंतिम स्तंभ तत्व [i] + सहायक (कीमत, विशेष, अस्थायी, i)
-
रिट :=न्यूनतम रिट और 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