我想编写一个小助手实用程序来组织我的数字化有声读物收藏。
我有一组需要写入 CD 的文件夹。文件夹不能拆分：每个文件夹都放在一个磁盘上。
我想最有效地填充磁盘：
- 最小化磁盘数量，以及
- 磁盘数量相等时，最大化最小填充磁盘的可用存储空间（
80 + 20剩余空间优于50 + 50）。
我应该使用哪种算法？
问问题
783 次
2 回答
4
这被称为装箱问题并且是 NP 难的，因此没有简单的算法来解决它。
我发现效果最好的解决方案（我举办了一个编程竞赛，问题几乎与此相同），是按大小对文件夹进行排序，然后将仍然适合光盘的最大文件夹放入光盘，直到它已满或所有剩余文件夹都太大以适应剩余空间。
这很快解决了这个问题，因为在排序之后算法的其余部分是 O(n)。
在我参加的比赛中，这导致了 74 个磁盘，而不是 79 个，而对于我们最大的测试数据集，一个简单的解决方案会达到。
于 2010-11-12T16:11:56.167 回答
2
如果您想在一张 CD-R光盘上打包文件/文件夹，那么您可以在伪多项式时间内以最佳方式完成此操作。为此，您必须将文件/文件夹的大小四舍五入为扇区，并计算 CD-R 上可用的扇区。
之后，我们得到离散的一维背包包装问题，可以使用动态规划很好地解决，复杂度为O(n)，
更加具体：
- O(n) = O(nW)，因为在您的情况下W是恒定的 - W 是 CD-R 上的扇区数量。
- n数量的文件/文件夹。
为了获得更好的性能，您始终可以过度估计扇区的大小，例如设置：
- 过度近似的扇区大小 70k
- 是什么让 700M/70k = CD-R 上所有扇区的 10k
- 当文件数量小于 (1G/10k=100k) 100k - n < 100'000时，应该以秒为单位计算
- n < 10'000'000时的分钟数
更重要的是：
- 解决方案可以很好地并行。
也许以贪婪的方式应用这个算法“打包一张CD，打包下一张CD”会起作用吗？
于 2011-08-24T11:35:51.450 回答