数据结构
网络
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 次浏览
广告