資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究C++ 中葡萄酒銷售獲利最大化
問題陳述
有一排 n 瓶葡萄酒，整數表示每瓶葡萄酒的價格。每年你可以賣掉這排酒的第一瓶或最後一瓶。葡萄酒的價格會隨著時間而上漲。設葡萄酒的初始利潤為 P1、P2、P3…Pn。在第 Y 年，第 i 瓶葡萄酒的利潤將為 Y*Pi。對於每一年，你的任務是列印 start 或 end，表示應銷售第一瓶或最後一瓶葡萄酒。此外，計算所有葡萄酒的最大利潤。
示例
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
更新於: 2020-01-21
149 次瀏覽
廣告