梱包の問題

Question

デジタル化されたオーディオブックコレクションを整理するために、小さなヘルパーユーティリティを書きたいです。

CDに書き込む必要があるフォルダーのセットがあります。フォルダーを分割することはできません。各フォルダーは1つのディスクになります。

ディスクを最も効率的に埋めたい：

1. ディスクの数を最小限に抑えます
2. 等しいディスクの数は、最小のディスクのストレージを最大化します（80 + 20 残りのスペースはより良いです 50 + 50).

どのアルゴリズムを使用する必要がありますか？

Answer 1

これはと呼ばれます ビンパッキングの問題 NPハードなので、それを解決する簡単なアルゴリズムはありません。

私が見つけたソリューションは、これとほぼ同じ質問でプログラミングコンテストを実行しました）は、サイズごとにフォルダを注文し、完全にまたはすべての残りのフォルダーが大きすぎるまでディスクに収まる最大のフォルダーを配置することでした残りのスペースに収まるように。

これにより、アルゴリズムの残りの部分はO（n）であるため、問題がすぐに解決されます。

私が実行したコンテストでは、最大のテストデータセットで素朴なソリューションが達成する79の代わりに74枚のディスクが発生しました。

Answer 2

ファイル/フォルダーを梱包したい場合 1つのCD-R ディスクは、擬似ポリノミナル時間でこれを最適に行うことができます。これを行うには、ファイル/フォルダーのサイズをセクターに丸め、CD-Rで利用可能なセクターをカウントする必要があります。

この後、私たちは取得します 個別の1-Dナップサックパッキングの問題, 、動的プログラミングを複雑に使用してうまく解決できます の上）,

具体的には：

• の上） = O（NW） 、 原因 w あなたの場合は一定です-WはCD -Rのセクターの量です。
• n ファイル/フォルダーの量。

パフォーマンスを向上させるために、セクターのサイズを承認しすぎると、セットアップの例があります。

• 過度に近接セクターサイズ70K
• CD-Rのすべてのセクターの700m/70k = 10kを作るもの
• （1g/10k = 100k）100k -when filesファイルが100k -onemindsで計算する必要があります。 n < 100'000
• 数分で n < 10'000'000

そのうえ：

• 解決策は、きれいに平行にすることができます。

たぶん、このアルゴリズムを貪欲な方法で適用する「1つのCD、Pack Next CD」はそれが機能しますか？