包装问题

Question

我想写一个小助手实用程序来组织我的数字化有声读物集合。

我有一组文件夹，需要写给CD。文件夹无法拆分：每个文件夹都进入一个磁盘。

我想最有效地填充磁盘：

1. 最小化磁盘的数量，并且
2. 磁盘的数量相等，最大化填充磁盘的可用存储空间（80 + 20 剩下的空间比 50 + 50).

我应该使用哪种算法？

Answer 1

这称为 垃圾箱包装问题 并且是NP-HARD，因此没有简单的算法来解决它。

我发现的解决方案最有效（我进行了一个与此相同的问题进行的编程比赛），是按大小订购文件夹，并将仍然适合光盘的最大文件夹放在光盘上，直到已满或所有其余的文件夹都太大适合其余空间。

这很快就解决了问题，因为在此类算法的其余部分为O（n）之后。

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

Answer 2

如果您想打包文件/文件夹 一个CD-R 光盘，比您在伪单学时最佳地做到这一点。为此，您必须将文件/文件夹的大小汇总到扇区中，并在CD-R上提供计数扇区。

之后，我们得到 离散的1D背包包装问题, ，可以使用动态编程可以很好地解决，并具有复杂性 上）,

更加具体：

• 上） = O（NW） ， 原因 w 在您的情况下是恒定的-W是CD -R上的扇区数量。
• n 文件/文件夹数量。

为了获得更好的性能，您总是可以过度陈述扇区，示例设置：

• 过度评估的部门尺寸70K
• 是什么使CD-R上所有部门的700m/70k = 10K
• 当数量少于（1g/10k = 100k）100K时，应在几秒钟内计算。 n < 100'000
• 在几分钟内 n < 10'000'000

更重要的是：

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

也许以贪婪的方式应用此算法“打包一张CD，Pack Next CD”是否可以工作？