Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

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।

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

  • memo नामक एक मैप परिभाषित करें
  • directPurchase() नामक एक विधि परिभाषित करें, यह कीमत और आवश्यकता सरणी लेता है
  • ret := 0
  • i को 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

  1. C++ में प्रोसेस मारें C++ में प्रोसेस मारें

    मान लीजिए हमारे पास n प्रोसेस हैं, यहां प्रत्येक प्रोसेस की एक अद्वितीय आईडी होती है जिसे PID या प्रोसेस आईडी कहा जाता है और इसका PPID (पैरेंट प्रोसेस आईडी) भी होता है। प्रत्येक प्रोसेस का केवल एक पैरेंट प्रोसेस होता है, लेकिन उसके एक या अधिक चाइल्ड प्रोसेस हो सकते हैं। यह एक ट्री संरचना की तरह है।

  1. C++ में गिलहरी सिमुलेशन C++ में गिलहरी सिमुलेशन

    एक पेड़, एक गिलहरी, और कई नट्स हैं। स्थितियों को 2D ग्रिड में सेल द्वारा दर्शाया जाता है। आपका लक्ष्य गिलहरी के लिए सभी नट्स को इकट्ठा करके उन्हें एक-एक करके पेड़ के नीचे रखने के लिए न्यूनतम दूरी ढूंढना है। गिलहरी एक समय में अधिकतम एक नट ले जा सकती है और चार दिशाओं में आगे बढ़ सकती है - ऊपर, नीचे,

  1. C++ में आयत क्षेत्रफल II (Rectangle Area II) - ओवरलैपिंग आयतों का कुल क्षेत्रफल C++ में आयत क्षेत्रफल II (Rectangle Area II) - ओवरलैपिंग आयतों का कुल क्षेत्रफल

    समस्या विवरण हमें अक्ष-संरेखित (axis-aligned) आयतों की एक सूची दी गई है। प्रत्येक आयत rectangle[i] = {x1, y1, x2, y2} द्वारा दर्शाया गया है, जहां (x1, y1) निचले-बाएं कोने का बिंदु है और (x2, y2) ऊपरी-दाएं कोने का बिंदु है। हमें तल (plane) में सभी आयतों द्वारा कवर किए गए कुल क्षेत्रफल को ज्ञात करना