C++で解く「料理の削減」問題：動的計画法によるライクタイム係数の最大化

問題の概要

あるシェフがいて、n個の料理それぞれについて満足度のデータを収集したとします。シェフはどの料理も1単位時間で調理できるものとします。

ここで、料理のライクタイム係数（Like-time coefficient）とは、その料理を調理するまでにかかった時間（それ以前の料理の調理時間を含む）に、その料理の満足度を掛けた値、すなわち time[i] * satisfaction[i] として定義されます。

求めたいのは、料理の準備を終えた後にシェフが得られるライクタイム係数の合計の最大値です。料理は任意の順序で調理でき、最大値を得るために一部の料理をあえて作らない（捨てる）ことも許されています。

例えば、入力が [-1,-7,0,6,-7] の場合、出力は 17 になります。2番目と最後の料理を取り除くと、ライクタイム係数の合計は次のように最大化されます。

-1×1 + 0×2 + 6×3 = 17

解決のためのアプローチ

この問題は、メモ化再帰（トップダウンDP）を用いた動的計画法で効率的に解くことができます。各料理について「作るか・作らないか」を選択し、その時点での経過時間を状態として管理するのがポイントです。

具体的には、以下の手順に従います。

• サイズ 505 × 505 の二次元配列 dp を定義します。
• 関数 solve() を定義します。引数はインデックス idx、現在の時間 time、配列 v です。
• idx が配列 v のサイズと等しい場合（すべての料理を判定し終えた場合）は、0 を返します。
• dp[idx][time] が -1 以外（計算済み）であれば、その値を返します。
• ret を負の無限大（INT_MIN）で初期化します。
• 「この料理を作らない場合」と「この料理を作る場合（v[idx] * time を加算し時間を1進める）」の大きい方を ret に代入します。
• dp[idx][time] に ret を記録して返します。

メイン関数側では、次の処理を行います。

• dp 配列全体を -1 で初期化します（未計算の印として使います）。
• 配列 v を昇順にソートします。これにより、満足度の低い（マイナスの）料理から先に検討でき、「採用しない」という選択を自然に表現できます。
• solve(0, 1, v) の結果を返します。

実装例

理解を深めるために、以下のC++による実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int dp[505][505];
    int solve(int idx, int time, vector <int>& v){
       if(idx == v.size()) return 0;
       if(dp[idx][time] != -1) return dp[idx][time];
       int ret = INT_MIN;
       ret = max(solve(idx + 1, time, v), v[idx] * time + solve(idx
       + 1, time + 1, v));
       return dp[idx][time] = ret;
    }
    int maxSatisfaction(vector<int>& v) {
       memset(dp, -1, sizeof(dp));
       sort(v.begin(), v.end());
       return solve(0, 1, v);
    }
};
main(){
    Solution ob;
    vector<int> v = {-1,-7,0,6,-7};
    cout << (ob.maxSatisfaction(v));
}

入力

{-1,-7,0,6,-7}

出力

17

まとめ

この問題の鍵となるのは、料理を満足度の昇順に並べ替えることと、各料理ごとに「作る／作らない」を再帰的に選択することです。メモ化により同じ状態（インデックスと時間の組み合わせ）の再計算を避けることで、計算量は O(n²) 程度に抑えられます。満足度がマイナスの料理でも、後続のプラスの料理との組み合わせ次第では合計を増やす可能性があるため、単純に負の値を除外するだけでは最適解が得られない点にも注意しましょう。