この欲張りアルゴリズムの証明例を教えてください。

Question

私はこの宿題の質問に問題があります。私は主な混乱は反例の根拠を特定しないことから来ていると思います。

let P1、。 。 。 、Pnは、ディスクに格納されたプログラムである。プログラムPiには Siメガバイトの記憶領域が必要で、ディスクの容量はD メガバイトです。 Dストレージ

• のメガバイトの合計よりも小さい場合（a）は、ディスクに開催されたプログラムの数を最大化します。プログラムを選択する欲張りアルゴリズムを証明するか、反例を与える：Si

• （b）できるだけ多くのディスク容量を使用する。反例を証明するか、与える：明確ではないため 申し訳ありません：Si

編集を減少させる 順にプログラムを選択貪欲アルゴリズム。

私の最初の試行では、プログラムが増加する順番に選択されていないと仮定していました（Si）。 Pa、PbおよびPcを選択してください。この後、私は実際にそれ以上に行く方法を理解していませんでしたが、パート（b）は同じ質問をしますが、Siを減らします。

Answer 1

a）定理：必要なディスク容量を増やしてプログラムを実行すると、できるだけ多くのプログラムが実行されます。証明：証明は矛盾によるものです。より多くのプログラムを実行できる他の方法があるとします。次に、この方法では、少なくとも1つのケースで異なるプログラムセットを選択する必要があります。すなわち、選択されていないものよりも多くのスペースを必要とする少なくとも1つのプログラムを選択しなければならない。しかし、この方法は、欲張りアルゴリズムによって選択されたものと区別するこの他のプログラムよりも、より少ない空間を必要とするプログラムを選択している可能性もある。これは、この方法が欲張り方法よりも優れているという仮定と矛盾する。したがって、貪欲方法よりも優れた方法はありません。最適です。定理：要求されるディスクスペースの順にプログラムを取っても、可能な限り多くのディスクスペースが使用されるとは限りません。証明：証明は例である。サイズが10のディスクと6,5,5のディスクスペースが必要なプログラムの場合を考えてみましょう。必要なディスクスペースの順にプログラムを実行すると、使用可能な10のストレージユニットのうち6つしか使用できませんが、2つのプログラム合計10ユニットにつき5ユニットが必要です。したがって、欲張りのアプローチは、すべての場合に最適な結果を与えるわけではありません。