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

Question

在给出数百兆字节不同大小的资产的情况下,填充一组蓝光光盘的最佳算法是什么？

我正在尝试整合大量旧的CDROMS,DVD和小型硬盘,并将所有内容放在由MD5签名索引的数据库中.肯定是一项艰巨的任务.

我目前所做的是按降序对资产大小(通常是目录大小)进行排序,开始插入填充列表中的最大资产,跳过任何不适合的资产,直到我用完资产.它几乎瞬间运行,但我不介意在必要时一夜之间运行.

它通常会给我95%或更高的利用率,但我确信有一种方法可以使用其他组合来提高效率.对于像磁盘映像这样的大型项目,我可以通过这种原始方法获得相当低的利用率.

我的想法是采取所有资产的组合,1然后是2,然后是3,...项目,并保持一个运行值,最高字节数<25,025,314,816字节,指向与之相加的数组.当我发现我一次拥有如此多的资产时,没有任何组合适合,停止并使用正在运行的最高计数器指向的数组.

这是最好的算法吗？

有2个Perl模块似乎可以完成任务,算法组合和算法组合.有什么建议更快,更稳定,更酷？

我的方案是编写一个脚本来计算大量目录的大小,并向我展示要刻录的数十个磁盘的最佳内容.

而且,我不想只是按文件填写文件,因为我想要在同一张光盘上的整个目录.

Answer 1

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

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

Answer 2

使用“背包”优化问题中的算法。

它可能不是最好的选择（它将最大化下一个磁盘的填充因子，而不是最小化所需的总磁盘数量），但它有很好的文档记录，并且很容易找到适合您选择的编程语言的示例和工作代码（甚至电子表格）在网络上。