什麼是最佳填充DVD刻錄的算法

Question

給定數百GB不同大小的資產，填充一套藍光光盤的最佳算法是什麼？

我想整合大量的舊CDROM，DVD和小硬盤，並將所有內容放入由MD5簽名索引的數據庫中。肯定是一項艱鉅的任務。

我目前所做的是按照降序對資產大小（通常是目錄大小）進行排序，開始在填充列表中插入最大的資產，跳過所有不適合的資產，直到資源用完。它幾乎是瞬間運行，但我不介意如果有必要一夜過夜。

它通常會給我95％或更多的利用率，但我相信有一種方法可以使用其他組合來提高效率。對於像磁盤映像這樣的大型項目，我可以通過這種原始方法獲得相當低的利用率。

我的想法是採取所有資產的組合，一次2，然後3，...一次，並保持一個運行值的最高字節數< 25,025,314,816字節指向數組，其總和它。當我得到一次只有很多資產都沒有被使用的情況時，停止並使用運行最高計數器指向的數組。

這是最好的算法嗎？

有2個Perl模塊可以完成任務，Algorithm-Combinatorics和Math-Combinatorics。任何建議更快，更穩定，更酷？

我的方案是編寫一個腳本來計算大量目錄的大小，並向我展示幾十個要刻錄的磁盤的最佳內容。

而且，我不想只是逐個文件地填充文件，因爲我希望整個目錄位於同一張光盤上。

Answer 1

使用「揹包」優化問題中的算法。

http://en.wikipedia.org/wiki/Knapsack_problem

1. 設定重量等於文件大小
2. 設置值等於「重量」
3. 運行的算法，以後每盤包裝

它可能不是最好的選擇（它會最大化下一個磁盤的填充因子，而不是最小化所需磁盤總數），但它有很好的文檔記錄並且很容易找到示例並在網絡上爲您選擇的編程語言（甚至是電子表格）提供工作代碼。

Answer 2

該算法被稱爲1d bin-packing。該算法速度非常快，但不是最優的。你也可以使用蠻力算法，但搜索空間非常大。這是一個貪婪算法程序：http://www.phpclasses.org/package/2027-PHP-Pack-files-without-exceeding-a-given-size-limit.html

Answer 3

這是一個NP完全問題，被稱爲bin packing。沒有已知的多項式時間算法可以最優地解決它。換句話說，如果沒有基本嘗試所有解決方案，就無法找到最佳解決方案。

另一方面，一個非常簡單的啓發式方法，如「將剩餘空間最大的文件夾放在第一個有空間的磁盤上」，將保證您使用的磁盤數量少於最佳情況的兩倍。 （你可以閱讀關於問題維基百科文章的更多細節）。

Answer 4

我發現最有效的方法可以有效地填充我的藍光光盤。

我列出了所有可用文件的完全限定路徑來刻錄。

然後（任意）決定有多少目錄級別考慮一堆或接受命令行選項。這是爲了讓目錄充滿類似的項目在一起的藍光。還有一個STUFF選項可以首先插入最大的文件，當文件導致溢出時，請查看下一個較小的文件，直到文件或空間用完。

對每個目錄做一個散列作爲它包含的文件的關鍵和總大小作爲數據。同時保留一個平行散列，每個目錄的文件數量因爲冗餘空間和目錄開銷明顯增加並且必須考慮在內。

選擇22作爲幻數。如果您有< = 22個目錄，請嘗試所有組合以找到最接近但不超過25.025 GB的那個 。如果你有超過22個，只需使用22個最大。我使用Perl模塊Algorithm :: Combinatorics來查找所有組合。通過試驗和大多數錯誤，我確定了21件物品的組合只需幾秒鐘。 23項需要很多分鐘，這比我的注意力範圍要長。 22大約需要35秒。

輸出目錄也被接受並檢查現有數據。有一個選項可以移動文件（複製，檢查大小和取消鏈接）。

每次我購買新的硬盤時，通常都是前一個硬盤的兩倍，所以我只會複製一切。憑藉尼康D800E（Extreme！），HDR和Panoramas，我終於耗盡了空間。

我的項目是獨特的，雜草和鞏固15年[大部分垃圾]照片，視頻，電影，音樂等價值。我盤查了大約十幾個存儲設備，計算MD5簽名並將它們全部放入數據庫。我選擇了一個驅動器作爲照片的主人，一個視頻的照片和其他一切。我找到了8份一些東西！

我現在有大約10TB的可用磁盤空間！

下面是在任何人感興趣的情況下做所有真實工作的功能。

============================================== = 糟糕！你的回答不能提交的原因是：

Your post appears to contain code that is not properly formatted as code 

愚蠢的網頁錯位我原始的代碼。對不起:(...