algorithm - 最佳填充 DVD 以进行刻录的算法是什么

Question

在给定数百 GB 不同大小的 Assets 的情况下，填充一组蓝光光盘的最佳算法是什么？

我正在尝试整合大量的旧 CDROM、DVD 和小型硬盘驱动器，并将所有内容放入一个由 MD5 签名索引的数据库中。这无疑是一项艰巨的任务。

我目前所做的是按降序对 Assets 大小(通常是目录大小)进行排序，开始在填充列表中插入最大的 Assets ，跳过任何不适合的 Assets ，直到 Assets 用完为止。它几乎是瞬间运行，但如果有必要，我不介意过夜运行一次。

它通常给我 95% 或更多的利用率，但我确信有一种方法可以使用其他组合来提供更高的效率。对于像磁盘镜像这样的大项目，我可以使用这种原始方法获得非常低的利用率。

我的想法是一次获取 Assets 的所有组合，1 然后 2，然后 3，... 项目并保持最高字节数 < 25,025,314,816 字节的运行值指向数组，该数组对其求和.当我达到我一次拥有如此多 Assets 以致于没有任何组合适合的地步时，停止并使用运行中的最高计数器指向的数组。

这是最好的算法吗？

有 2 个 Perl 模块似乎可以胜任这项任务，Algorithm-Combinatorics 和 Math-Combinatorics。有什么更快、更稳定、更酷的建议吗？

我的方案是写一个脚本来计算大量目录的大小，并显示几十个要刻录的磁盘的最佳内容。

而且，我不想逐个文件地填充文件，因为我希望整个目录都在同一张光盘上。

Answer 1

这是一个 NP 完全问题，称为 bin packing .没有已知的多项式时间算法可以最优地解决它。换句话说，如果不基本上尝试所有解决方案，就无法找到最佳解决方案。

从好的方面来说，一个非常简单的试探法，如“将最大的剩余文件夹放在第一个有空间的磁盘上”将保证您使用的磁盘数量少于最佳情况的两倍。 (您可以在该问题的维基百科文章中阅读更多详细信息)。