সমস্যা বিবরণ
এক সারিে n সংখ্যক ওয়াইন আছে, যাদের প্রত্যেকের দাম.Integer আকারে দেওয়া আছে। প্রতিবর্ষ আপনি সারিটির প্রথম বা শেষ ওয়াইনটি বিক্রি করতে পারেন। ওয়াইনগুলোর দাম সময়ের সাথে বাড়ে। প্রারম্ভিক লাভগুলো হল P1, P2, P3…Pn। Y-তম বছরে, i-তম ওয়াইনটির লাভ হবে Y*Pi। প্রতিবর্ষের জন্য, আপনার কাজ হল প্রিন্ট করা 'start' বা 'end' যাতে বোঝা যায় প্রথম বা শেষ কোন ওয়াইনটি বিক্রি করতে হবে। এছাড়াও সব ওয়াইন থেকে সর্বোচ্চ লাভ হিসাব করতে হবে।
উদাহরণ
যদি ওয়াইন দামগুলো {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
