我想编写一个小工具来组织我的数字化有声读物收藏。我有一组需要写入光盘的文件夹，这些文件夹不能被拆分：每个文件夹都需要写入一张光盘。我希望尽可能高效地填满光盘：
- 最小化光盘数量
- 如果光盘数量相等，则最大化最空闲光盘的可用存储空间（剩余空间为 80 + 20 比 50 + 50 更好）。
2个回答
4
这被称为装箱问题，它是NP难问题，因此没有简单的算法可以解决它。
我找到的最好的解决方案（我运行了一个编程竞赛，提出了一个几乎与此相同的问题），是按大小排序文件夹，并将最大的适合光盘的文件夹放入，直到光盘已满或所有剩余文件夹都太大而无法放入剩余空间。
由于排序后，算法的其余部分是O(n)，因此这个解决方案可以快速解决问题。
在我举办的比赛中，这导致使用74张光盘，而朴素解决方案会使用79张光盘来处理我们的最大测试数据集。
- Alan Geleynse
3
谢谢。鉴于当前CD-R的价格，我认为即使是一个非最优解决方案，我也能够生存下去。维基页面提到了几种算法，您是否知道一些实现方式？ - Quassnoi
@Quanssnoi 我更新了答案，包括一个我见过可行的相当简单的解决方案。 - Alan Geleynse
1我找到了这个：http://sourceforge.net/projects/bin-packing/ 经过一些改进，我认为它会起作用。我真的需要安装一个支持闪存驱动器的汽车音频设备。 - Quassnoi
2
如果您想将文件/文件夹打包到一个CD-R光盘上，那么您可以在伪多项式时间内最优地完成此操作。为此，您需要将文件/文件夹的大小舍入到扇区，并计算CD-R上可用的扇区数。
之后，我们得到了离散一维背包问题，可以使用动态规划很好地解决，复杂度为O(n)，
更具体地说：
之后，我们得到了离散一维背包问题，可以使用动态规划很好地解决，复杂度为O(n)，
更具体地说：
- O(n)=O(nW)，因为在您的情况下，W是常量- W是CD-R上的扇区数量。
- n是文件/文件夹的数量。
- 过度逼近的扇区大小为70k
- 这使得700M/70k = 10k成为CD-R上所有扇区的数量
- 当文件数量小于(1G/10k=100k) 100k - n < 100'000时，应该在几秒钟内计算出来
- 当n < 10'000'000时，应该在几分钟内计算出来
此外：
- 解决方案可以很好地并行化。
也许以贪婪的方式应用这个算法"装一个光盘，装下一个光盘"会起到作用？
- Grzegorz Wierzowiecki
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接