7

ファイルのリスト (大きいものと小さいもの) を取得し、それらを DVD (または CD など) にできるだけ効率的に収めるアプリケーションを作成する必要があります。このアプリケーションの全体的なポイントは、2 番目のディスクに移動する前に 1 番目のディスクをできるだけ使い果たし、3 番目のディスクに移動する前に 2 番目のディスクをできるだけいっぱいにする、などです。

(注: アプリケーションは、DVD への実際の書き込みを行う必要はありません。可能な限り最適なものを見つけ出す必要があるだけです)。

最初は、ファイルの順列を生成し、各組み合わせをチェックして最適なものを確認することで、良いゲームプランがあると思いました. (これに関する私のリクエストは、こちらで見つけることができます)

しかし、ファイルが多ければ多いほど、時間がかかります...指数関数的に。そのため、これを達成する最善の方法について意見を求めました。

何か案は？そして、いつものように、C# コードは常に高く評価されています。

4

9 に答える 9

12

あなたが直面しているのは、ナップザックの問題に関連しています。リンクされたウィキペディアのページには、解決方法の提案など、さらに多くの情報があります。

于 2010-09-29T20:03:58.550 に答える
9

単純なアルゴリズム:

  1. ファイル リストをファイル サイズで並べ替える
  2. DVD の残りの空き容量よりも小さい最大のファイルを見つけて、DVD に追加します。
  3. 残りの DVD の空き容量が残りのファイルよりも少ない場合は、新しい DVD を開始します。
  4. 2から繰り返します。
于 2010-09-29T20:18:27.080 に答える
2

この質問にまだ興味がある人のために...ファイルを一連のディスク/ディスクに収めるという同様の目的で使用するユーティリティを作成しました。コマンドライン/ファイルベースのインターフェイスを使用します。バージョンは、C、C++、および Java (C# ではありません) で利用できます。

http://whizman.com/code/diskfit.tgz

より詳細な情報は、diskfit.tgz:Doc/diskfit.txt ファイルにあります。

(AGPL3)

この質問は、0-1 の複数のナップザック、または線形ビン パッキングとして特徴付けることができます。(ナップザックの問題に関するリンクを提供してくれた jon-skeet に感謝します。)

Dthorpe は線形ビン パッキングを解決し、すべてのファイルにちょうど十分なビン/ディスクが収まるようにします [適切に O(n) または O(n lg n) 高速 - スクリプトを書かなくてもスプレッドシートで実行できる場合もあります]。

基本的に、diskfit (上記のリンク先のユーティリティ) は、0 ～ 1 個のシングル ナップザックに基づいて適格なファイル セットを出力し、ユーザーは 1 つのディスク ファイル セットを選択してディスク セットにアセンブルします - ユーザーを支援します (ただし、完全に自動化するわけではありません)。両方に向かって:

  • リニア ビン パッキング - 完全なディスク セット用。
  • 0 から 1 の複数のナップザック - ディスク 1..k の各サブセットのフル ディスク セット (ファイルが優先される場所、つまり値が異なります)。

このような完全なディスクセットをプログラムで完全に選択することは、追加機能になります。ディスクごとに [貪欲に] 自動的に 0-1 のシングル ナップザック ソリューションを適用するだけでは不十分です。(容量 6 の 3 つのナップザックと、同等の価値と重量を持つ利用可能なアイテムを考えてみましょう: {1, 1, 2, 2, 3, 4, 5}。0-1 のナップザックを最初のナップザックに単独で適用すると、{1, 1, 2, 2} を使用して合計値 4 を取得します。その後、残りの 3 つのアイテムすべてを残りの 2 番目と 3 番目のナップザックに収めることはできませんが、{1, 2, 3 のように 3 つのナップザックにすべてのアイテムを収めることができます。 } & {1, 5} & {2, 4}.)

于 2012-10-17T00:26:45.827 に答える
1 
for each file
 is there enough room this dvd?
   yes, store it here
   no, is there room on another already allocated dvd?
     yes, store it there
     no, allocate another dvd and store it there
于 2010-09-29T20:09:28.200 に答える
1

特定のアプリケーションのプログラムで解決するのはクールな問題ですが...しかし、アプリケーションでは、アーカイブを特定のサイズのファイルチャンクに分割する機能を持つWinRARまたはその他のアーカイブプログラムを使用しないでください。各チャンクを DVD のサイズにしてから、ただ焼き尽くすことができます。

編集: 遭遇する問題の 1 つは、ファイルの 1 つがメディアのサイズよりも大きい場合、そのファイルを書き込むことができないということです。

于 2010-09-29T20:19:11.290 に答える
0

この問題を解決すると思われる多くのツールを見つけましたが、それらはすべて、使用されるディスクの総数を最小限に抑えようとしますが、SINGLE ディスクに最適なファイルの SINGLE サブセットに興味があっただけです。

それで、「ss」と呼ばれる独自のツールの作成を終了しました（「サブセット合計」アルゴリズムに基づく）。このツールにはまだバグがあり、ディレクトリを再帰することはできませんが、私にとってはうまく機能しています。:)

于 2012-12-14T19:40:55.687 に答える
0

できる限り大きなファイルを 1 枚の DVD に入れることから始めて、できる限り多くの小さなファイルを (最小のファイルから始めて) いっぱいにすることから始めたらどうでしょうか。

各ディスクの残りのファイルでこのプロセスを繰り返します。

それがあなたに完璧なカバレッジ/ディストリビューションを提供するかどうかはわかりませんが、あなたのニーズを解決するのに役立つかもしれないと思います.

于 2010-09-29T21:14:01.483 に答える