Lợi nhuận tối đa từ việc bán rượu vang bằng C ++

Tuyên bố vấn đề

Cho n loại rượu liên tiếp, với các số nguyên biểu thị giá thành của mỗi loại rượu tương ứng. Mỗi năm bạn có thể bán rượu đầu tiên hoặc rượu cuối cùng trong hàng. Giá của các loại rượu tăng lên theo thời gian. Gọi lợi nhuận ban đầu từ các loại rượu là P1, P2, P3… Pn. Vào năm thứ Y, lợi nhuận từ rượu thứ i sẽ là Y * Pi. Đối với mỗi năm, nhiệm vụ của bạn là in bắt đầu hoặc kết thúc cho biết rượu vang đầu tiên hay cuối cùng nên được bán. Ngoài ra, hãy tính toán lợi nhuận tối đa từ tất cả các loại rượu.

Ví dụ

If wine prices are {2, 4, 6, 2, 5} then output will be:
start end end start start
Maximum profit = 64

Thuật toán

Chúng tôi có thể sử dụng lập trình động để giải quyết vấn đề này -

• Ý tưởng là lưu trữ hành động tối ưu cho mỗi trạng thái và sử dụng hành động đó để điều hướng qua các trạng thái tối ưu bắt đầu từ trạng thái ban đầu

Ví dụ

#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;
}

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra đầu ra tiếp theo -

start end end start start
Maximum profit = 64