次の問題を解決するためにどのような戦略を使用する必要があるかを知りたいです。
問題文
2 つの炭鉱があり、それぞれが鉱山労働者のグループを雇用しています。私たちの仕事は、食料品を鉱山に送ることです。食糧が鉱山に到着するたびに、鉱山労働者はある程度の量の石炭を生産します。食品の出荷には、肉、魚、パンの 3 種類があります。
新しい積荷が鉱山に到着するたびに、彼らは新しい積荷と前の 2 つの積荷 (またはそれほど多くない場合はより少ない積荷) を考慮し、次のことを行います。
- すべての積荷が同じタイプの場合、1 単位の石炭が生産されます。
- 積荷の中に 2 種類の異なる食品がある場合、それらは 2 単位の石炭を生産します。
- 3 種類の異なる食料がある場合、それらは 3 単位の石炭を生産します。
食品の配送の種類と配送順序は事前にわかっています。
入力
食品の発送の種類が、発送される順序で示されます。
ゴール
目標は、石炭生産量を最大化することです。これは、どの貨物がどの鉱山に行くべきかを決定することによって行われます。2 つの鉱山は必ずしも同じ数の貨物を受け取る必要はありません (実際、すべての貨物を 1 つの鉱山に送ることは許可されています)。
例
出荷オーダー: MBMFFB の場合、期待される生産量 (可能な最大石炭生産量) は 12 です。