C＃：用于尽可能高效地将大量文件放入DVD的代码
我需要编写一个应用程序，它将获取一个文件列表（一些大的，一些小的），并尽可能高效地将它们放到DVD（或CD或其他）上。 本应用的重点是在移动到第二张光盘之前尽可能多地使用第一张光盘，在移动到第三张光盘之前尽可能多地填充第二张光盘，等等。
（注意：应用程序不必对DVD进行实际刻录，只需要找出最合适的效果）。
我最初认为我有一个很好的游戏计划，通过生成文件的排列，然后检查每个组合，看看什么是最合适的。 （我的求助请求可以在这里找到）
但是文件越多，所需的时间就越长……指数级。 所以我希望你对如何最好地实现这一点有一些看法。
有任何想法吗？ 而且，一如既往，C＃代码总是受到赞赏。
简单的算法：
- 按文件大小对文件列表进行排序
- 找到小于DVD上剩余可用空间的最大文件，并将其添加到DVD。
- 如果剩余的DVD可用空间小于任何剩余文件，请启动新的DVD。
- 重复2。
你所面临的问题与背包问题有关 。 链接的维基百科页面包含更多信息，包括建议的解决方法。
对于仍然对这个问题感兴趣的人…我写了一个实用工具，我用它来将文件装入一组磁盘/光盘。 它使用基于命令行/文件的界面。 版本有C，C ++和Java（不是C＃）。
http://whizman.com/code/diskfit.tgz
更详细的信息在diskfit.tgz：Doc / diskfit.txt文件中。
（AGPL3）
我们可能将问题描述为0-1多背包或线性箱包装。 （感谢jon-diaet关于背包问题的链接。）
Dthorpe解决了线性bin包装，对于足够的箱/盘来适应所有文件[很快O（n）或O（n lg n）快速 – 在电子表格中也可行，而无需编写脚本]。
基本上，diskfit（上面链接的实用程序）输出基于0-1单背包的合格文件集，并且用户选择单磁盘文件集来组装到磁盘集中 – 协助用户（但不是完全自动化）对于两者：
- 线性箱包装 – 用于完整的磁盘组;
- 0-1多个背包 – 对于每个磁盘子集1..k的整个磁盘集（其中文件优先，值也不同）。
完整的这种磁盘集的完全程序化选择将是一个额外的function。 应用0-1单背包解决方案是不够的，通过光盘自动盘[贪婪]。 （考虑3个容量为6的背包，以及具有相同数值和重量的可用物品：{1,1,2,2,3,4,5}。将0-1背包单独应用于第一个背包将选择{1， 1,2,2}获得总和值4 – 之后我们无法在剩下的第二和第三背包中容纳所有剩余的3个项目 – 而我们知道我们可以将3个背包中的所有项目都安装为{1,2,3 }＆{1,5}＆{2,4}。）
for each file is there enough room this dvd? yes, store it here no, is there room on another already allocated dvd? yes, store it there no, allocate another dvd and store it there 虽然这对于某些应用程序的程序来说是一个很酷的问题…但是在您的应用程序中，为什么不使用WinRAR或其他一些能够将存档拆分为特定大小的文件块的归档程序。 您可以使每个块大小与DVD相同，然后烧掉。
编辑：您将遇到的一个问题是，如果您的某个文件大于您的媒体大小，您将无法刻录该文件。
如果你开始把尽可能多的最大文件放到一张DVD上，然后用尽可能多的最小文件填充它（从最小的文件开始）。
对每个磁盘的剩余文件重复此过程。
我不确定这会给你完美的报道/分发，但我认为它可能会在某种程度上解决你的需求。
使用回溯来获取要刻录到DVD 1的最佳文件集，然后将它们从列表中排除并使用其余文件的回溯来获得dvd 2的最佳填充等等
我发现了许多应该解决这个问题的工具，但它们都试图最小化所用光盘的TOTAL数量，而我只对最适合SINGLE光盘的SINGLE文件子集感兴趣。
所以我结束了自己编写的名为“ ss ”的工具（来自“子集和”算法）。 该工具仍然有问题，无法递归目录，但它对我有用。 🙂
这个问题是Bin装箱问题并且是NP完整的，这意味着如果你想要一个真正的最佳解决方案，你将需要指数时间。 然而，有些方法提供的解决方案不是最优，但运行速度要快得多。
假设我们有一个无限的磁盘列表。 将每个文件的大小按顺序递减，然后将每个文件添加到它适合的第一个磁盘中。这称为First fit decrease，在最坏的情况下需要11/9 OPT + 6/9磁盘。 如果您以随机顺序选择文件，则需要11/9 OPT + 1个磁盘。
有些算法会将事情收紧，请参阅上面的维基百科链接以获取更多详细信息。