algorithm - 貯水スケジュール

Question

MIB の本部にはN 個の水タンクがあります。タンクiは最大でc _i単位の水を貯蔵できます。各タンクには、独自の流入パイプと流出パイプがあります。タンクiの流入パイプはレートu _iで水を漏らします。つまり、タンクiに 100 単位の水を入れたい場合、100/(1 - u _i ) の水が消費されます。流出パイプはすべて完璧です。それらの容量はin _iとout _iです。つまり、タンクiの流入パイプは最大で_{iを運ぶことができます。}1 単位時間 (漏出を含む) 内の水単位、および出口パイプは 1 単位時間内に最大で_i単位の水を運ぶことができます。

整数シーケンスw _t (1 < t < T) は、この貯水システムにどれだけの水を入れることができるか、またはどれだけの水を取り出さなければならないかを表します。たとえば、(5, 3, -8, 10) は、システムが 1 番目、2 番目、および 4 番目のタイム スロットで最大 5、3、および 10 ユニットの水を取り込むことができ、3 番目のタイム スロットで 8 ユニットの水を排出する必要があることを意味します。タイムスロット。排出水の量が要件に違反する場合、実行不可能と呼ばれます (取水要件に違反しても問題ありません)。問題は、各タンクのパラメーター ( c _i、u _i、in _i、out _i ) とシーケンスw _t、すべてのアウトレット要件を満たすことが可能な天候ですか? 時刻 0 ではすべてのタンクが空です。

N < 10,000、T < 10,000

ありがとう

Answer 1

まず第一に、これは単独では機能しないスキームです。これは、流入と流出の最大レートに関する制約を無視し、より簡単な問題を解決するためです。

ここで難しいのは、どのタンクをいつ使用するかということです。Ui の値が低い戦車ほど優れているようです。スペースのある Ui の値が低いタンクがあるときに、Ui の値が高いタンクを満たすシーケンスを使用する場合、最初に良いタンクを満たし、余分な水を使用することで、より良いシーケンスを得ることができます。そうでなければ、より悪いタンクに入れる水を使用します。同様に、良いタンクに水があるときに悪いタンクから水を抽出している場合、良いタンクから水を抽出することでより良いシーケンスを得ることができます。タンク。

そのため、タンクに水を入れるときは利用可能な最高のタンクに水を入れたいと考え、タンクを空にするときは利用可能な最高のタンクを空にしたいように見えます。これを考えると - そして、あなたが言及していない制限がないことを前提として - 転送中の整数量の水など - どのような状況でも最適なスケジュールを見つけるのは簡単に思えます. したがって、この最適なスケジュールを試してみてください。うまくいかない場合は、何もできません。

制約を無視したため、上記は機能しません。私は確かに流入率と流出率を無視しました。また、各ステップで複数のタンクを使用できると仮定していますが、そうではないかもしれません.

より単純な問題を解決する他のスキームがあります。流出率以外のすべての制約を無視し、各段階で可能な最大の流出率でタンクを満たし、需要を満たすことができる最低の流出率でタンクから水を供給することができます。

これらのバリアントは問題を解決しませんが、いくつかの制約を無視したときに解決策がない場合、元の問題の解決策はありません。これは、分岐限定のバリアントにつながります。

1) 単純なグリード ソリューションで適切なスケジュールが見つかった場合、シーケンスは明らかに解決可能です。

2) 簡単な問題を解いてみてください。それらのいずれかが解決できない場合、このシーケンスの解決策はありません。

3) 最初の時間ステップで考えられるすべての選択肢を検討し、タンク内の水から始めて、結果として得られる短いシーケンスを再帰的に解決します。それらのいずれかが解決策を見つけるとすぐに、あなたはそれを返すことができます. すべてをチェックして、すべて「解決策なし」と表示されている場合、解決策はありません。