問題を説明する名前がわからないので、その例を設定し、力ずくで解決するよりも優れたアルゴリズムについて助けを求めます。
6 つのバケットがあり、それぞれが異なるサイズで、それぞれが異なる開始ボリュームを保持しています。各バケツには、バケツがいっぱいになったときに分配される賞金 (お金と呼びます) へのリンクもあります。
8つのバルブがあります。各バルブは、開いたときに異なるバケットのサブセットを供給し、バルブが開いたときに各バケットに異なる量を追加できます。各バルブには固定コストがあります。
部分的な例: バケット 1: 20 ガロンの 14。$2.00 を支払う バケット 2: 25 ガロンのうち 12 ガロン。$1.50 を支払う バケット 3: 35 ガロンの 18。$4.00などを支払う...
バルブ 1: $0.50 の費用がかかります。2 ガロンを 2 に、1 ガロンを 3 に入れます。バルブ 2: $0.40 の費用がかかります。1 に 3 ガロン、2 に 5 ガロンなどを入れます。
つまり、お金を払ってバルブを回し、バケツを満たすとお金を獲得できます。
目的: 収益性の高い組み合わせが存在する場合、バケットがいっぱいになったときに純利益が最大になるバルブの最適な順序を計算します。
バケットがいっぱいになると、事前設定された開始量にリセットされます (現在の量とは異なる場合があります - バケットはバルブの回転からバルブの回転まで状態を保持します)。理論的には、リセットの回数に制限がないため、バルブを永遠に回す可能性があります。
ここでの明白な解決策はブルートフォースです。変数を開始位置にリセットし、1 つのバルブを回し、出力をテストし、リセットし、次のバルブまで繰り返します。8 つすべてを回したら、2 つのバルブ (11、12、13、14、... 25、26) を回し始めます。 、27、28)。少なくとも 1 つのバケットを満たす組み合わせを見つけるたびに、純利益/損失を計算し、以前の結果と比較して最良のものを決定します。
遅くて粗雑。かなり直接的ですが、遅くて粗雑です。
そう：
- このタイプの問題の名前は何ですか? と
- それをより効率的に解決するのに役立つ既知のアルゴリズムはありますか?
明確にするために - 数学の詳細は改善が必要なビットではありません - 数学のわずかな違いに関係なく、バルブ操作の任意のシーケンスの結果を簡単に計算できます。
私が避けたいのは力ずくの繰り返しです。8 回の単一操作 (v1、v2、v3...)、次に 64 回の二重操作 (v1v1、v1v2、v1v3 など)、512 回の三重操作 (v1v1v1、v1v1v2、v1v1v3) を実行したくありません。それを避けることができます。