0-1マルチディメンションナップザックの最大キャパシティ利用を求める

Question

0-1マルチディメンションナップザックの典型的な目的関数は、ナップザックのすべてのアイテムの価値を最大にすることです。良いアルゴリズムはStackexchangeのリンクにあります：0-1 Multidimensional Knapsack。

しかし、私の目的は、できるだけ多くのアイテムをナップザックにパックすることです。すべてのピースは等しい値を持ちます。 Stackexchangeの投稿（Knapsack problem with all profits equal to 1）は、貪欲アルゴリズムによって等しい値を持つ一次元のナップザックを解決できると主張しています。本当？私は01ナップザックの問題はNP困難だと思ったので、貪欲なアルゴリズムは最適な解決法を与えられないかもしれません。

私の質問は2部構成ですか？ 1）この場合、グリーディアルゴリズムによって最適解を与えることができますか？ 01同じ値のナップザック 2）多次元貪欲アルゴリズムの実装方法？ vi/wiはベクトルで割った値です。

Answer 1

1.）ナップザック問題はNP困難な問題です。要するに、欲張りなアルゴリズムを使って最適に解決することはできません。その代わりに、ヒューリスティックなアプローチが存在し、非常に近いことができます。

2.）均等利益ナップザックの場合、これはシンプルなビンの詰め込みの問題になりがちです。この文脈では、すべての選択肢が利益の面で等しい場合、おそらく「サイズ」のような問題の別の側面に焦点を当てる必要があります。そのような場合は、毎回できる最小のアイテムを選びたいと思うでしょう。その場合、欲張りアルゴリズムではおそらく十分であり、選択肢を見て最小の要素を選ぶだけで達成できます。

リニア検索では、繰り返し実行するとプログラムに煩わしいオーバーヘッドが加わることがあります。代わりにMIN-Heapを使用することを検討すると、より少ない計算コストで最小の値を利用できるようになります。