包装问题
我想编写一个小助手实用程序来组织我的数字化有声读物收藏。
我有一组文件夹需要写入 CD。文件夹无法拆分：每个文件夹都位于一张磁盘上。
我想最有效地填充磁盘：
- 最小化磁盘数量，并且
- 磁盘数量相等，最大化最少填充磁盘的可用存储空间（
80 + 20剩余空间优于50 + 50）。
我应该使用哪种算法？
I want to write a little helper utility to organize my digitized audiobooks collection.
I have a set of folders which I need to write to CDs. The folders can not be split: each folder goes onto one disk.
I want to fill the disks most efficiently:
- Minimize the number of disks, and
- The number of disks being equal, maximize the storage available of the least filled disk (
80 + 20remaining space is better than50 + 50).
Which algorithm should I use?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这称为装箱问题，并且是 NP 困难的，因此没有一个简单的算法可以解决解决它。
我发现效果最好的解决方案（我参加了一个编程竞赛，问题几乎与此相同），是按大小对文件夹进行排序，并将仍然适合光盘的最大文件夹放入光盘中，直到它已满或所有剩余的文件夹太大以适应剩余空间。
这很快就解决了问题，因为排序后算法的其余部分是 O(n)。
在我参加的比赛中，这导致了 74 个光盘，而不是我们最大的测试数据集的简单解决方案所能达到的 79 个光盘。
This is called the Bin Packing Problem and is NP-hard, so there is not a simple algorithm to solve it.
The solution I found worked best (I ran a programming contest with a question almost identical to this), was to order the folders by size and put the largest folder that still fits onto the disc until it is full or all remaining folders are too large to fit in the remaining space.
This solves the problem quickly since after the sort the rest of the algorithm is O(n).
In the contest I ran, this resulted in 74 discs instead of the 79 that a naive solution would achieve for our largest test data set.
如果您想将文件/文件夹打包到一张 CD-R 光盘上，那么您可以在伪多项式时间内以最佳方式完成此操作。为此，您必须将文件/文件夹的大小四舍五入为扇区，并计算 CD-R 上可用的扇区。
之后，我们得到离散一维背包打包问题，其中可以使用动态规划很好地解决，复杂度为 O(n)，
更具体地说：
为了获得更好的性能，您始终可以过度近似扇区大小，示例设置：
更重要的是：
也许以贪婪的方式应用这个算法“打包一张CD，打包下一张CD”会起作用吗？
If you would like to pack files/folders on one CD-R disc, than you could do this optimally in pseudo-polynominal time. To do this, you have to round sizes of files/folders into sectors, and count sectors available on CD-R.
After this, we get discrete 1-D knapsack packing problem, which can be solved nicely using dynamic programming, with complexity O(n),
To be more specific:
For better performance you can always over-approximate size of sectors, example setup:
What's more:
Maybe applying this algorithm in greedy manner "pack one cd, pack next cd" will do it's work?