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

C++ में वाइन की बिक्री से अधिकतम लाभ


समस्या कथन

एक पंक्ति में n वाइन दी गई हैं, जिनमें प्रत्येक वाइन की लागत को दर्शाने वाले पूर्णांक हैं। प्रत्येक वर्ष आप पंक्ति में पहली या आखिरी वाइन बेच सकते हैं। वाइन की कीमत समय के साथ बढ़ती है। मान लें वाइन से प्रारंभिक लाभ P1, P2, P3…Pn हैं। Yवें वर्ष में, ith वाइन से लाभ Y*Pi होगा। प्रत्येक वर्ष के लिए, आपका कार्य स्टार्ट या एंड प्रिंट करना है जो दर्शाता है कि पहली या आखिरी वाइन बेची जानी चाहिए। साथ ही सभी वाइन से अधिकतम लाभ की गणना करें।

उदाहरण

यदि वाइन की कीमतें {2, 4, 6, 2, 5} हैं तो आउटपुट होगा: start end end start start Maximum profit = 64

एल्गोरिदम

हम इस समस्या को हल करने के लिए डायनामिक प्रोग्रामिंग का उपयोग कर सकते हैं −

  • विचार प्रत्येक स्टेट के लिए इष्टतम एक्शन को स्टोर करना और प्रारंभिक स्टेट से शुरू करके इष्टतम स्टेट्स के माध्यम से नेविगेट करने के लिए उसका उपयोग करना है

उदाहरण

#include <bits/stdc++.h> using namespace std; #define N 1000 int dp[N][N]; int sell[N][N]; int maxProfitUtil(int price[], int begin, int end, int n) {    if (dp[begin][end] != -1) {       return dp[begin][end];    }    int year = n - (end - begin);    if (begin == end) {       return year * price[begin];    }    int x = price[begin] * year + maxProfitUtil(price, begin + 1, end, n);    int y = price[end] * year + maxProfitUtil(price, begin, end - 1, n);    int ans = max(x, y);    dp[begin][end] = ans;    if (x >= y) {       sell[begin][end] = 0;    } else {       sell[begin][end] = 1;    }    return ans; } int maxProfit(int price[], int n) {    for (int i = 0; i < N; i++) {       for (int j = 0; j < N; j++) {          dp[i][j] = -1;       }    }    int ans = maxProfitUtil(price, 0, n - 1, n);    int i = 0, j = n - 1;    while (i <= j) {       if (sell[i][j] == 0) {          cout << "start ";          i++;       } else {          cout << "end ";          j--;       }    }    cout << endl;    return ans; } int main() {    int price[] = { 2, 4, 6, 2, 5 };    int n = sizeof(price) / sizeof(price[0]);    int ans = maxProfit(price, n);    cout << "Maximum profit = " << ans << endl;    return 0; }

आउटपुट

जब आप उपरोक्त प्रोग्राम को कंपाइल और चलाएंगे। यह निम्नलिखित आउटपुट उत्पन्न करेगा −

start end end start start Maximum profit = 64

  1. C++ में जॉब शेड्यूलिंग में अधिकतम लाभ (Maximum Profit in Job Scheduling) C++ में जॉब शेड्यूलिंग में अधिकतम लाभ (Maximum Profit in Job Scheduling)

    समस्या विवरण n अलग-अलग कार्य दिए गए हैं। प्रत्येक कार्य startTime[i] से endTime[i] तक चलता है और profit[i] लाभ देता है। हमें ऐसे कार्यों का सबसेट चुनना है जिनके समय ओवरलैप न हों, ताकि कुल लाभ अधिकतम हो। यदि एक कार्य समय X पर समाप्त होता है, तो दूसरा कार्य समय X पर शुरू हो सकता है। उदाहरण इनपुट sta

  1. - C++ में एरे से अधिकतम परिमाप वाला त्रिकोण

    समस्या कथनगैर-ऋणात्मक पूर्णांकों का एक एरे दिया गया है। एरे से तीन तत्व ढूंढें जो अधिकतम परिमाप वाला त्रिकोण बनाते हैं।उदाहरणयदि इनपुट एरे {5, 1, 3, 5, 7, 4} है तो अधिकतम परिमाप (7 + 5 + 5) = 17 हैएल्गोरिदमएरे को गैर-बढ़ते क्रम में सॉर्ट करें। तो, पहला तत्व अधिकतम होगा और अंतिम न्यूनतमयदि इस सॉर्ट क

  1. - C++ में ट्री से अधिकतम एज हटाकर ईवन फॉरेस्ट बनाना

    समस्या कथन एक अनडायरेक्टेड ट्री दिया गया है जिसमें सम संख्या में वर्टेक्स हैं। हमें इस ट्री से अधिकतम संख्या में एज हटाने की आवश्यकता है ताकि परिणामी फॉरेस्ट के प्रत्येक कनेक्टेड कंपोनेंट में सम संख्या में वर्टेक्स हों। उदाहरण ऊपर दिखाए गए ट्री में, हम अधिकतम 2 एज 0-2 और 0-4 हटा सकते हैं (लाल रंग