ダイナミックプログラミング - 最大の利益を出して販売するワイン

Question

N個のワインが棚に並んでいるとしましょう。ワインの価格はパイです。 （異なるワインの価格は異なる場合があります）。今年のワインは毎年良くなるので、今年は1年であると仮定すると、i番目のワインの価格はy * pi、すなわち現在の年のy倍になります。 あなたは持っているすべてのワインを売りたいが、今年からは1年に1本のワインを売りたい。もう1つの制約 - 毎年、左または右のワインだけを棚に入れて販売することが許可されています。棚のワインを並べ替えることはできません（つまり、ワインは最初と同じ順序で留まる必要があります）。 ワインを最適な順序で販売する場合、最大の利益は何ですか？

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. をするために必要な条件を書くコスト選びますベースケースは

はのはthis--

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

のためのC++プログラムを書いてみましょう

私は上記のコードを考えては、自己exlanatoryある
のは、それを実行してみましょう：

Input1: 
5 
1 
3 
1 
5 
2 
Output: 
43 

Input2: 
4 
10 
1 
10 
9 
Output: 
79 

上記のコードの時間複雑さはnがノーであるO（2^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）であろう。