সমস্যা বিবৃতি
পরপর 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
