☰

是否有实用程序可以将文件最佳地分发到多张 DVD 上？

tag-icon • tag-icon dvd media burning performance algorithm
是否有实用程序可以将文件最佳地分发到多张 DVD 上？

我有一堆媒体文件想要刻录到 DVD 上，但由于每张 DVD 只能容纳 4.5GB，我必须找到最佳的方式来组织文件以使用最少数量的 DVD（否则每张 DVD 中剩余的空白空间很容易累积起来）。有什么工具可以帮助解决这个问题吗？

许多年前，有一个 DOS 实用程序可以利用软盘执行此操作。

答案1

免费试用DVD 跨度：

DVD Span 是一款备份工具，用于将大文件夹的内容写入多张 DVD。DVD Span 可以自动确定每张磁盘的最佳组织方式，以便在最少数量的磁盘上容纳最大数量的数据。DVDSpan 是一款出色的工具，可用于将您的音乐收藏、照片甚至整个硬盘备份到 DVD。而且由于它可以制作普通 DVD（或 CD），因此无需特殊软件即可读取或恢复您的备份。

答案2

啊，背包问题。我只能找到一个在线解算器来解决这个问题，这里。您的背包大小为 4.5GB，每个数据包都是您的文件大小。您需要稍微调整一下其输出以适合您的特定应用程序，但它应该是可行的。但这不会运行得很快，因为这个问题是难的。

答案3

概述

Jeff Shattock 的回答是正确的，这等同于（或同构，正如数学家所写）组合优化问题，但它等同于一维装箱问题，而不是背包问题。

幸运的是，我有一些代码可以为您或任何其他人解决这个问题，只要他们能访问安装了至少 3.5 版 .NET Framework 的 Windows 计算机。

粗略的解决方案

  1. 首先，下载并安装LINQPad。

  2. 二、下载我刚刚写的 LINQPad 查询– 这是原始文件的 linq (ha)。将其保存为.linq文件并在 LINQPad 中打开它。

  3. 更改参数：

    这是您应该更改的 LINQPad 查询代码中的部分：

    int binSizeMb = 4476; // This is the (floor of the) total size of a DVD+R reported by CDBurnerXP. string rootFileFolderPath = @"F:\2006 - Polyester Pimpstrap Intergalactic Extravaganza multicam";

    更改binSizeMb为您的“容器”的大小，例如 CD、DVD，例如int binSizeMb = 650;CD。

    笔记– 该binSizeMb值被解释为有时被称为兆字节。与我小时候所有字节倍数都是“二进制”的情况相反，现在有时“MB”指的是“十进制兆字节”或正好 1,000,000 字节，而不是我的代码中使用的兆比字节 (MiB) 的 1,048,576 字节。如果您想更改这一点，请将const int bytesPerMb = 1048576;代码中的行更改为const int bytesPerMb = 1000000;。

    更改rootFileFolderPath为包含您想要“打包到箱子里”的文件的文件夹的完整路径，例如string rootFileFolderPath = @"C:\MySecretBinFilesFolder";。

  4. 通过点击F5或单击执行查询选项卡左上角的按钮。

结果

查询代码将递归地枚举文件夹中的所有文件rootFileFolderPath，这意味着它也将包括所有子文件夹中的文件。

然后它将为文件创建“bin”，使得每个 bin 中所有文件的总大小小于或等于指定的 bin 大小。

在 LINQPad 结果窗格中您将看到两个列表。

第一个列表是它找到的所有文件，按大小降序排列。

第二个列表是通过“打包文件”创建的容器，其中包含文件及其大小的列表，以及容器的剩余大小。

下面的屏幕截图显示了第二个列表和创建的前两个箱子：

LINQPad 屏幕截图显示了容器列表

粗略分析

根据维基百科，我使用的算法 - 首次适应递减（FFD）策略 - 应该不会太糟糕；维基百科指出：

2007 年，已证明 FFD 的界限 11/9 OPT + 6/9 是紧的。

“OPT” 是指最优策略（指可能无法实现的策略，而不是任何特定的实际策略）。

根据我对所涉及的数学术语的模糊记忆，这应该意味着 FFD 策略在最坏的情况下应该将物品装入最佳策略的约 1.22 倍的箱子中。因此，该策略可能会将物品装入 5 个箱子而不是 4 个。我怀疑，除了特定的“病态”物品尺寸外，它的性能可能非常接近最佳性能。

同一篇维基百科文章还指出，“精确算法”。我可能也会决定实现这一点。我必须先阅读描述该算法的论文。

答案4

您可以在哈斯克尔的搭车指南，也许是在完成了该教程的某些部分之后；该教程是围绕解决您的问题而编写的，即将内容分配到多个磁盘上，从而逐步完善解决方案，如以下段落所示第3章本教程的内容：

准备工作已经足够了。我们去打包一些 CD 吧。

你可能已经意识到，我们的问题是一个经典问题。它被称为“背包问题” （谷歌一下，如果你还不知道它是什么的话。有超过 100000 个链接）。

让我们从贪婪的解决方案开始......

更多想法：相关问题

这是一个类似的问题（虽然不一样：那里没有要求进行优化），您可以在其中找到更有用的解决方案/程序来完成您的任务（如果它们被发布的话）：

建议的教程中有一些关于理解编程的提示

总的来说，Haskell 代码非常具有表现力（因为 Haskell 是一种高抽象层次的编程语言），因此很容易掌握。

当查看其中一个解决方案的代码时，请记住，我们要编写的程序的顶层结构非常简单，如下所示第1章本教程的内容：

现在让我们思考一下我们的程序将如何运行，并用伪代码来表达它：

main = Read list of directories and their sizes.
       Decide how to fit them on CD-Rs.
       Print solution.

听起来合理吗？我认为是这样。

让我们稍微简化一下，现在假设我们将在程序之外的某个地方计算目录大小（例如，使用“ du -sb *”）并从标准输入中读取此信息。

并进一步仔细地研究解决方案的各个部分。

相关内容