包装问题 [英] Packing problem

问题描述

我想写一个小帮手工具来整理我的数字化有声读物收藏。

I want to write a little helper utility to organize my digitized audiobooks collection.

我有一组，我需要写到CD文件夹。该文件夹不能分割：每个文件夹进入到一个磁盘

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:

1. 最小化的磁盘数量，和
2. 的磁盘相等的数量，增加可用最少的填充磁盘（存储 80 + 20 剩余空间小于 50 + 50好）。

1. Minimize the number of disks, and
2. The number of disks being equal, maximize the storage available of the least filled disk (80 + 20 remaining space is better than 50 + 50).

我应该使用哪种算法？

推荐答案

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

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.

这迅速解决了问题，因为排序后的算法的其余部分是O（n）。

This solves the problem quickly since after the sort the rest of the algorithm is O(n).

在我跑的较量，这导致了74盘，而不是79，一个天真的解决方案将实现我们的最大的测试数据集。

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.

这篇关于包装问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！