समस्या कथन
एक पंक्ति में n वाइन दी गई है, जिसमें पूर्णांक क्रमशः प्रत्येक वाइन की लागत को दर्शाते हैं। हर साल आप पंक्ति में पहली या आखिरी शराब बेच सकते हैं। शराब की कीमत समय के साथ बढ़ती जाती है। बता दें कि वाइन से शुरुआती लाभ P1, P2, P3…Pn है। Yth वर्ष पर, ith वाइन से लाभ Y*Pi होगा। प्रत्येक वर्ष के लिए, आपका कार्य यह दर्शाता है कि पहली या आखिरी शराब बेची जानी चाहिए या नहीं, प्रिंट करना शुरू करें या समाप्त करें। साथ ही, सभी वाइन से अधिकतम लाभ की गणना करें।
उदाहरण
If wine prices are {2, 4, 6, 2, 5} then output will be:
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