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