大量のデータストアを使用する大量のマシンがあります。すべてのマシンのデータを新しいデータ ストアに転送したいと考えています。これらの新しいストアでは、マシンで使用できるストレージ スペースの量が異なります。さらに、保存する必要があるデータの量はマシンごとに異なります。1 台のマシンのすべてのデータは、1 つのデータ ストアに格納する必要があります。分割することはできません。それ以外は、データがどのように配分されるかは問題ではありません。
現在、スペースよりも多くのデータがあるため、データが見つかるまで、一部のマシンでデータをそのままにしておく必要があることは避けられません. それまでの間、私たちが持っているストレージに最適またはほぼ最適な割り当てを提供するアルゴリズム（比較的単純です：私はそれほど賢くない）を知っている人はいますか（つまり、割り当て後に新しいストアに残っているスペースの最小量） )?
これは宿題の問題のように聞こえるかもしれませんが、本当のことを保証します!
一見すると、これは複数のナップザック問題 ( http://www.or.deis.unibo.it/knapsack.html、第 6.6 章「複数のナップザック問題 - 近似アルゴリズム」) のように見えるかもしれませんが、実際にはスケジューリングの問題です。時間要素が含まれているからです。言うまでもなく、この種の問題を解決するのは複雑です。1 つの方法は、それらをネットワーク フローとしてモデル化し、GOBLIN のようなネットワーク フロー ライブラリを使用することです。
あなたの場合、実際にはストアを最適に埋めたくないことに注意してください。そうすると、より小さなデータパッケージが保存される可能性が高くなります。大きなパッケージが機械に残っていると、将来のパッキングがますます悪化するため、これは悪いことです. あなたがしたいことは、たとえそれが店舗により多くの余分なスペースを残すことを意味するとしても、より大きなパッケージを保管することを優先することです.
簡単なアルゴリズムでこの問題を解決する方法は次のとおりです。
(1) ビンのサイズを決定し、並べ替えます。たとえば、スペースが 20 GB、45 GB、および 70 GB の 3 つのストアがある場合、ターゲットは { 20, 45, 70 } です。
(2) すべてのデータ パッケージをサイズ順に並べ替えます。たとえば、{ 2, 2, 4, 6, 7, 7, 8, 11, 13, 14, 17, 23, 29, 37 } というデータ パッケージがあるとします。
(3) いずれかのパッケージの合計が店舗の 95% を超える場合、それらをその店舗に入れ、ステップ (1) に進みます。ここではそうではありません。
(4) 2 つのパッケージの順列をすべて生成します。
(5) いずれかの順列の合計がストアの 95% を超える場合、それらをそのストアに配置します。同点の場合は、より大きなパッケージとの組み合わせを優先します。私の例では、{ 37, 8 } = 45 と { 17, 2 } = 19 の 2 つのペアがあります ({ 17, 2 } を使用すると、{ 13, 7 } を使用した場合よりも優先されることに注意してください)。1 つ以上の一致が見つかった場合は、手順 (1) に戻ります。
さて、残っているのは 1 つのストアだけです: 70 と次のパッケージ: { 2, 4, 6, 7, 7, 11, 13, 14, 23, 29 }.
(6) パーマの数を 1 増やして、ステップ 5 に進みます。たとえば、私たちの場合、70 の 95% 以上に 3 パーマを追加することはなく、4 パーマ { 29, 23, 14, 4 } を追加することがわかります。 = 70. 最後に、マシンに残っているパッケージ { 2, 6, 7, 7, 11, 13 } が残ります。これらはほとんどが小さいパッケージであることに注意してください。
perms は字句の逆順 (大きいものが先) でテストされることに注意してください。たとえば、e が最大の "abcde" がある場合、3-perms の字句の逆順は次のようになります。
cde
bde
ade
bce
ace
など
このアルゴリズムは非常に単純で、状況に応じて適切な結果が得られます。