समस्या कथन
एक पंक्ति में 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