7

我需要编写一个应用程序,它将获取文件列表(一些大的,一些小的)并尽可能高效地将它们放入 DVD(或 CD 或其他任何东西)上。这个应用程序的重点是在移动到第二个圆盘之前用完尽可能多的第一个圆盘,在移动到第三个圆盘之前尽可能多地填充第二个圆盘,等等。

(注意:应用程序不必对 DVD 进行实际的刻录,它只需要找出最适合的方式)。

我最初认为我有一个很好的游戏计划,通过生成文件的排列然后检查每个组合以查看最适合的组合。(我在这方面的帮助请求可以在这里找到)

但是文件越多,花费的时间就越长……成倍增长。所以我想听听你对如何最好地实现这一目标的看法。

有任何想法吗?而且,一如既往,C# 代码总是受到赞赏。

4

9 回答 9

12

您面临的问题与背包问题有关。链接的维基百科页面包含更多信息,包括建议的解决方法。

于 2010-09-29T20:03:58.550 回答
9

简单算法:

  1. 按文件大小对文件列表进行排序
  2. 找到小于 DVD 上剩余可用空间的最大文件,并将其添加到 DVD。
  3. 如果剩余的 DVD 可用空间小于任何剩余文件,请启动新的 dvd。
  4. 从 2 开始重复。
于 2010-09-29T20:18:27.080 回答
2

对于仍然对这个问题感兴趣的任何人......我编写了一个实用程序,用于将文件装入一组磁盘/光盘的类似目的。它使用基于命令行/文件的界面。有 C、C++ 和 Java(不是 C#)版本。

http://whizman.com/code/diskfit.tgz

更多详细信息在 diskfit.tgz:Doc/diskfit.txt 文件中。

(AGPL3)

我们可以将这个问题描述为 0-1 多重背包或线性装箱。(感谢 jon-skeet 提供有关背包问题的链接。)

Dthorpe 解决了线性 bin 打包问题,以获得足够的 bin/disks 以适应所有文件 [很好地 O(n) 或 O(n lg n) 快速 - 在电子表格中也可能是可行的,而无需编写脚本]。

基本上,diskfit(上面链接的实用程序)输出基于 0-1 单背包的合格文件集,并且用户选择一个磁盘文件集组装到磁盘集 - 协助用户(但不是完全自动化)对两者:

  • 线性箱包装 - 用于完整的磁盘组;
  • 0-1 多重背包 - 对于完整磁盘集的磁盘 1..k 的每个子集(其中文件优先,也就是值不同)。

完整的此类磁盘集的完整编程选择将是一个附加功能。应用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}。)

于 2012-10-17T00:26:45.827 回答
1
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
于 2010-09-29T20:09:28.200 回答
1

虽然这是在某些应用程序的程序中解决的一个很酷的问题......但是在您的应用程序中,为什么不使用 WinRAR 或其他能够将存档拆分为特定大小的文件块的存档程序。您可以将每个块制作成 DVD 的大小,然后直接烧掉。

编辑:您会遇到的一个问题是,如果您的文件之一大于媒体的大小,您将无法刻录该文件。

于 2010-09-29T20:19:11.290 回答
0

如果您首先将尽可能多的最大文件放在一张 DVD 上,然后用尽可能多的最小文件填充它(从最小的文件开始),怎么样。

对每个磁盘的剩余文件重复此过程。

我不确定这会给你完美的覆盖/分布,但我认为它可能会在某种程度上解决你的需求。

于 2010-09-29T21:14:01.483 回答
0

使用回溯获取要刻录到 dvd 1 的最佳文件集,然后将它们从列表中排除,并对剩余文件使用回溯以获得 dvd 2 的最佳填充,依此类推

于 2012-09-03T14:57:41.947 回答
0

我找到了很多可以解决这个问题的工具,但它们都试图最小化使用的磁盘总数,而我只是对最适合单张光盘的文件的单子集感兴趣。

所以我已经结束了编写我自己的名为“ ss ”的工具(来自基于的“子集和”算法)。该工具仍然存在问题并且无法递归目录,但它对我有用。:)

于 2012-12-14T19:40:55.687 回答
0

这个问题是装箱问题并且是 NP 完全的,这意味着如果你想要一个真正的最优解,你将需要指数时间。然而,有些方法给出的解决方案不是最优的,但运行速度要快得多。

假设我们有一个无限的磁盘列表。取每个按大小降序排列的文件,然后将每个文件添加到它适合的第一个磁盘。这称为 First fit 递减,在最坏的情况下占用 11/9 OPT + 6/9 个磁盘。如果您以随机顺序选择文件,则需要 11/9 OPT + 1 个磁盘。

有一些算法可以让事情变得更紧密,请参阅上面的维基百科链接了解更多详细信息。

于 2014-08-06T23:00:22.680 回答