包装问题

Question

我想写一个小助手实用程序来组织我的数字化有声图书收藏。

我有一套文件夹，我需要写到CD。文件夹不能分割:每个文件夹都会转到一个磁盘上。

我想最有效地填充磁盘：

1. 最大限度地减少磁盘数量，
2. 如果磁盘数量相等，则最大限度地利用填充最少的磁盘的可用存储空间(80 + 20剩余空间优于50 + 50)。

我应该使用哪种算法？

Answer 1

这就是所谓的装箱问题，是NP硬的，所以没有简单的算法来解决它。

我发现的解决方案最有效(我运行了一个与此几乎相同的问题的编程竞赛)，就是按大小顺序排列文件夹，并将仍然适合的最大文件夹放到磁盘上，直到磁盘满了，或者所有剩余文件夹都太大，无法容纳剩余的空间。

这很快地解决了这个问题，因为排序之后，算法的其余部分是O(n)。

在我运行的比赛中，这导致了74个光盘，而不是一个天真的解决方案将实现我们最大的测试数据集79光盘。

Answer 2

如果您想要将文件/文件夹打包到的一个CD-R光盘上，那么您可以在伪多标称时间内最优地进行此操作。为此，必须将文件/文件夹的大小整成扇区，并计算CD-R上可用的扇区。

在此之后，我们得到了离散一维背包包装问题，它可以用动态规划很好地解决，复杂度为O(n)，

更具体而言：

• O(n) = O(nW)，因为W在你的情况下是不变的-W是CD-R上扇区的数量。
• N文件/文件夹的数量。

为了获得更好的性能，您可以总是超过近似的扇区大小，例如设置：

• 过近似扇形尺寸70k
• 什么使70万/70k= 10k的所有部门的CD-R
• 当文件数量小于(1G/10k=100 k)100 k-n< 100'000时，应以秒计算。
• 数分钟内，当n<10,000‘000

更重要的是

• 解决方案可以很好地并行。

也许以贪婪的方式应用这个算法“打包一张cd，打包下一张cd”会做它的工作吗？