ビンパッキング問題の変化に使用される欲張りアルゴリズムの証明

Question

我々は、重みの配列を与えられます $ w $ （すべての重みは正の整数です）、 ビンの中の重み。各ビンは最大のMAX_VALを保持することができ、各重みは最大のMAX_VALです。バリエーションは、重みの順序を変更しないでください、すなわち $ w_i $ は $の前にbinの内側にあるべきです。w_j $ は、すべての $ i に対して挿入されます。

この問題の声明については、直感的に私たちはその最大値に達するまでの貪欲なアプローチと、さらなる重みのための新しいビンを作成することが最小のビン数を生み出すでしょう。私は、欲張り解が最適であるという正式な証明を思いつくことができません。ヒントやガイドラインは素晴らしいでしょう！

Answer 1

$ g $ は、欲張りアルゴリズムによって生成された解です。互いに互いに解決済み $ S $ 、 $ i（s）$ を最初の重みのインデックスにする $ s $ の $ g $ から分岐します。 $ o $ を最適なソリューションで、 $ i（o）$ を最大化します。したがって、 $ g $ の場所 $ i（o）$ のbin $ J $ （ $ j $ ）、および $ o $ の場所< span class="math-container"> $ i（o）$ bin $ J + 1 $ 。 $ i（o）$ を移動すると、 $ j $ （ $ O $ 順序付けられています）、 $ o '$ を $ O $ 、およびspan class="math-container"> $ i（o '）> i（o）$ を満たします。これは、 $ o $ の選択と矛盾します。

無制限のBINパッキングアルゴリズムでこの引数を実行しようとすると、 $ i（o）$ をbin $ i（o）$ i（o）$ i（o）のための十分なスペースを残していないので、math-container "> $ J $ は他の要素で占められている可能性があるため、そのビンが他の要素で占有される可能性があります。あなたが考えるバリアントでは、これは起こり得ません。