用C ++出售葡萄酒可获得最大利润

问题陈述

连续给出n种葡萄酒，其中整数分别表示每种葡萄酒的价格。每年您都可以出售该行中的第一个或最后一个葡萄酒。葡萄酒的价格随着时间的流逝而上涨。让葡萄酒的初始利润为P1，P2，P3…Pn。在第Y年，第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