动态规划 - 以最大利润销售葡萄酒

Question

假设您有一个 N 种葡萄酒的集合，彼此相邻地放在架子上。第i种葡萄酒的价格是圆周率。(不同葡萄酒的价格可能不同)。因为葡萄酒每年都变得更好，假设今天是1年，在第y年，第i种葡萄酒的价格将是y*pi，即y乘以当年的价值。 你想卖掉你所有的葡萄酒，但你想从今年开始，每年只卖一种葡萄酒。还有一个限制 - 每年你只允许出售货架上最左边或最右边的葡萄酒，并且不允许重新订购货架上的葡萄酒(即它们必须保持与开始时相同的顺序)。 您想了解，如果您以最佳顺序出售葡萄酒，您可以获得的最大利润是多少？

int N; // number of wines 
int p[N]; // array of wine prices
int cache[N][N]; // all values initialized to -1 
int profit(int be, int en) {
if (be > en)
return 0;
if (cache[be][en] != -1)
return cache[be][en];
int year = N - (en-be+1) + 1;
return cache[be][en] = max(profit(be+1, en) + year * p[be],profit(be, en-1) + year * p[en]);
}

时间复杂度：O(n^2)。 我已经找到了这个 O(n^2) 解决方案。我们可以在 O(n) 中做到这一点吗？(更好的时间复杂度)

Answer 1

您应该通过出售货架上的所有葡萄酒来找到最佳成本。唯一的限制是你只能挑选左边或右边的葡萄酒(你不能从架子中间挑选一个酒瓶)。由于我们可以选择左边或右
边的葡萄酒，因此最佳解决方案的顺序将包括左瓶或右瓶。
让我们为此找到一个递归解决方案。

1. 只需拿起左边的瓶子并计算其成本
2. 拿起合适的瓶子并计算成本
3. 比较成本并选择最大成本
4. 为基本情况编写必要的条件

让我们为此编写一个 c++ 程序--

#include<bits/stdc++.h>
using namespace std;
int max_cost(int wine[], int cost, int counter, int i, int j){

// Here `counter` keeps track of the number of years
// `i` is the left indices of the shelf
// `j` is the right indices of the shelf
// `cost` is the maximum cost that we have to find

if(i > j)
return cost;
else if(i == j){
cost += counter * wine[i];
return cost;
}
else{
int cost1 = counter * wine[i] + max_cost(wine, 0, counter + 1, i + 1, j);
int cost2 = counter * wine[j] + max_cost(wine, 0, counter + 1, i, j - 1);
cost += max(cost1, cost2);
return cost;
}
}
int main(){
int n;
cin >> n;
int wine[n];
for(int j = 0; j < n; ++j)
cin >> wine[j];
cout << max_cost(wine, 0, 1, 0, n - 1) << endl;
return 0;
}

我认为上面的代码是自我
解释的 让我们运行它：

Input1:
5
1
3
1
5
2
Output:
43
Input2:
4
10
1
10
9
Output:
79

上述代码的时间复杂度为 O(2^n)，其中n是货架上酒瓶的数量。
我们可以即兴发挥时间复杂度吗？
当然。我们基本上是一遍又一遍地计算一些序列，这是可以通过记忆技术来避免的。
递归关系将基本相同。除此之外，我们还将记住特定i的值和j。因此，我们不必一次又一次地计算相同i和j的值。
c++ 代码将是 --

#include<bits/stdc++.h>
using namespace std;
int find_cost(vector<int>& box, vector<vector<int>>& dp, int i, int j){
if(i == j)        // base case
dp[i][j] = box[i] * box.size();
else if(!dp[i][j]){        // If not calculated so far
int n = box.size();
dp[i][j] = max(find_cost(box, dp, i, j - 1) + box[j] * (n - (j - i)), 
find_cost(box, dp, i + 1, j) + box[i] * (n - (j - i)));
}
return dp[i][j];
}
void cost_wine(vector<int> box){
int n = box.size();
vector<vector<int>> dp(n + 1, vector<int>(n + 1));  // Initialize dp array
cout << find_cost(box, dp, 0, n - 1);
return;
}
int main(){
int n;
cin >> n;
vector<int> box(n);
for(int i = 0; i < n; ++i)
cin >> box[i];
cost_wine(box);
return 0;
}

现在上面代码的时间复杂度将是 O(n^2)，这比递归方法要好得多。