バックパックのタスク：内部には何がありますか？

彼の投稿の名誉あるSergeyACTIVITIは、バックパックの問題などの有用なことを教えてくれました。その解決策は、COIN-ORまたはGLPKソルバーで正常に実装されました。 そして中身は何ですか？



したがって、ボリュームWのバックパックとn個のリストを用意します。各リストにはボリュームv [i]と値c [i]があり、それぞれを何度でも使用できます。 さらに、すべてのボリュームとすべての値は正の整数になります。 アルゴリズムはどのように機能しますか？



最大長W + 1の配列を開始します。この配列では、アルゴリズムの結果に応じて、 特定のボリュームを占めるもののセットが持つことができる最高のコストを取得します。

より正確には、k回の反復の後、各ボリュームi max [i]について取得します。これは、最初のk個の物のみが可能な、ボリュームiの物のセットの最大可能コストです。

最初はmax [0] = 0を初期化する必要があることがすぐにわかります。maxの他の要素は何ですか？ 何も使用しないと、0の体重増加しか得られません。したがって、max [i]（0 <i <= W）では、体重増加iの可能性のあるコストよりも悪い何かを書く必要があります。 たとえば、-1。

その後、n回の反復を行う必要があります。



k番目の反復で、次のことを行います。

反復の前に、各要素max [i]の配列に、重みiの物のセットの最大可能コストが書き込まれます。これは、物0..k-1で構成されます。 毎回、要素max [i]を考慮して、物事0..kで構成される、重量物iのセットの最大可能コストが書き込まれるようにします。 これを行うには、最適なセットに一般にk番目の要素があり、少なくとも1つあることを確認します。 そうでない場合、最大コストはすでにmax [i]に書き込まれています。 存在する場合、このセットから1番目のk個がスローされると、ボリュームiv [k]の最適なセットが残り、0..kから残ります。 しかし、後者はすでにmax [iv [k]]で記述されています！ したがって、値max [i]とmax [iv [k]] + c [k]を比較するだけです（もちろん、i> = v [k]でない限り）。 それらの最大値は、max [i]で記述する必要があります。

したがって、k回目の反復の後、各max [i]に、物で構成される物のセットが持つことができる最高値を取得します。 したがって、n回の反復の後、約束されたとおりの結果が得られます。 これは技術的な問題です。max[i]配列を調べて、その中の最大要素を選択します。

ご覧のとおり、アルゴリズムの漸近的な動作はO（W * n）であり、使用されるメモリはO（W）です。



バリエーション：

1.コストだけでなく、セット自体も取得する必要がある場合 。

max配列に加えて、prev配列も記述します。 その中に、最後にセットに入れたものを書き留めます。 つまり、max [i]とmax [iv [k]] + c [k]を比較すると、max [iv [k]] + c [k]の方が優れていることが判明した場合、最適な重みコレクションではi k番目の主題である。 したがって、最適なコストmax [i]が重みiを獲得することによって達成されることがわかった場合、prev [i]をセットに追加したと書くことができます。 そして、最適な体重増加i-v [prev [i]]に進みます。 そこにも、最後に何が取られたかがわかります。 など、ゼロに達するまで。



2.各アイテムを1回のみ摂取できる場合 。

ここではさらに簡単です。下から上ではなく、上から下、つまりWから0まで、各反復で配列を通過する必要があります。その後、max [iv [k]]を検討すると、そこにセットが書き込まれます重量i-v [k]の最大コストは、0..k-1のものだけを使用して取得できます。 したがって、最適なセットでk番目のものを使用する必要があることが判明した場合、1回だけ使用されます。



3.可能な限りこれに近い値の選択。

コストがない場合、このアルゴリズムは明らかにバックパックを可能な限り満たすのに役立ちます。 または、バックパックに関するものではなく、物の合計量がバックパックの量以下であることが重要でない場合は、追加することで複数の数字からこれにできるだけ近い数字を追加できます。



すべての場合において、動作時間と使用されるメモリの漸近的な動作は同じです。



4.各物が特定の回数服用できる場合。

このバリエーションの口紅をありがとう。

0からq [i]回まで番号iを持つものをとることができる問題のバリエーションがあります。 もちろん、i番目のものをq [i]単位で「乗算」して、0-1バックパックの問題を解決できます。 ただし、このようなソリューションの複雑さはO（W * ∑q [i]）になり、あまり良くありません。 実際、あなたはより巧妙なことができます。



q [i] = 1 + 2 + 4 + 8 + ... + 2 ^ k + r [i]とする。ここでr [i] <2 ^（k + 1）。

次に、ボリュームが1 * v [i]、2 * v [i]、...、2 ^ k * v [i]、r [i] * v [i]、コストが1 * c [i]のk + 2個のアイテムを検討します。 ]、2 * c [i]、...、2 ^ k * c [i]、r [i] * c [i]、それぞれ。

（新しいアイテムの「名前」-「1番目のアイテム」、「2番目のアイテム」、「4番目のアイテム」など）



これらのk + 2項目の異なるサブセットを選択することにより、タイプiの任意の数（0からq [i]）のものを取得できることは明らかです。 つまり、i番目のタイプのものをq [i]単位で「乗算」する代わりに、k + 2 = O（log q [i]）単位に制限することができました。



このような方法は、次数O（W * ∑log q [i]）の複雑さを持ち、「単純な」ソリューションよりもはるかに効率的です。



PS気にする人、あなたはウィキペディアの記事を編集することができます-それは何かが間違っていると言います=）