C++で解くワイン販売問題:動的計画法で最大利益と最適な売却順序を求める

問題の概要

n本のワインが一列に並んでおり、各ワインの価格を表す整数が与えられます。毎年、列の先頭または末尾にあるワインを1本売ることができます。ワインの価値は年月とともに上昇し、初年度の各ワインの利益を P1, P2, P3, …, Pn とすると、Y年目における i 番目のワインの利益は Y × Pi で表されます。毎年、先頭のワインを売る場合は「start」、末尾のワインを売る場合は「end」を出力し、最終的にすべてのワインから得られる最大利益を計算してください。

入力例

ワインの価格が {2, 4, 6, 2, 5} の場合、出力は以下のようになります:
start end end start start
最大利益 = 64

アルゴリズム

この問題は動的計画法(DP)を用いて効率的に解くことができます。

• まだ売っていないワインの範囲を区間 [begin, end] として管理し、各区間ごとの最大利益を dp 配列に記録してメモ化することで、同じ状態の再計算を防ぎます。
• 現在の年数は year = n − (end − begin) で求められます。これは、これまでに売却済みのワインの本数に相当します。
• 「先頭のワインを売る場合」と「末尾のワインを売る場合」のそれぞれの利益を計算し、大きい方を採用します。同時に、どちらを選んだかを sell 配列に記録しておきます。
• 最後に sell 配列を先頭から順にたどることで、最適な売却順序(start / end)を復元できます。

状態数は O(n²)、各状態の計算は O(1) であるため、時間計算量・空間計算量はいずれも O(n²) となります。

実装例(C++)

#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