C++でのワインの販売による最大の利益

問題の説明

n個のワインが連続して与えられ、整数はそれぞれ各ワインのコストを示します。毎年、列の最初または最後のワインを販売できます。ワインの価格は時間とともに上昇します。ワインからの初期利益をP1、P2、P3…Pnとします。 Y年目には、i番目のワインからの利益は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