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

给定数百GB不同大小的资产，填充一套蓝光光盘的最佳算法是什么？什么是最佳填充DVD刻录的算法

我想整合大量的旧CDROM，DVD和小硬盘，并将所有内容放入由MD5签名索引的数据库中。肯定是一项艰巨的任务。

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

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

我的想法是采取所有资产的组合，一次2，然后3，...一次，并保持一个运行值的最高字节数< 25,025,314,816字节指向数组，其总和它。当我得到一次只有很多资产都没有被使用的情况时，停止并使用运行最高计数器指向的数组。

这是最好的算法吗？

有2个Perl模块可以完成任务，Algorithm-Combinatorics和Math-Combinatorics。任何建议更快，更稳定，更酷？

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

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

来源

2012-07-27 user1556337

-2

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

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

设定重量等于文件大小
设置值等于“重量”
运行的算法，以后每盘包装

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

来源

2012-07-27 01:15:24 anttix

编号Knappsack有2个变量 – Bytemain 2012-07-27 01:19:26

那么是什么？你可以设置所有的元素为1的“值”为例 – anttix 2012-07-27 01:23:09

当然，你可以这样做，但它是否适用于公制字节和千字节？它是虚拟的 – Bytemain 2012-07-27 01:25:23

该算法被称为1d bin-packing。该算法速度非常快，但不是最优的。你也可以使用蛮力算法，但搜索空间非常大。这是一个贪婪算法程序：http://www.phpclasses.org/package/2027-PHP-Pack-files-without-exceeding-a-given-size-limit.html

来源

2012-07-27 01:16:01 Bytemain

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

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

来源

2012-07-27 01:21:00 chepner

我发现最有效的方法可以有效地填充我的蓝光光盘。

我列出了所有可用文件的完全限定路径来刻录。

然后（任意）决定有多少目录级别考虑一堆或接受命令行选项。这是为了让目录充满类似的项目在一起的蓝光。还有一个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

愚蠢的网页错位我原始的代码。对不起:(...

来源

2012-10-18 22:40:53 user1556337

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

回答

相关问题