对于仍然对这个问题感兴趣的任何人......我编写了一个实用程序,用于将文件装入一组磁盘/光盘的类似目的。它使用基于命令行/文件的界面。有 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}。)