找到最佳文件大小组合

Question

这是一个问题,我认为已经有一个算法 - 但我不知道正确的话使用谷歌似乎:).

问题:我想创建一个小程序,我将选择一个包含任何文件的目录(但我的目的是媒体文件,音频和视频).之后,我想以MB输入不得超过的最大文件总大小.此时,您将点击"计算最佳拟合"按钮.

此按钮应比较目录中的所有文件,并提供一个文件列表,这些文件放在一起时最接近最大文件总大小而不超过限制.

这样,您可以在刻录CD或DVD时找出要合并的文件,以便您可以尽可能多地使用光盘.

我试图为此自己提出算法 - 但失败了:(.

有人知道一些很好的算法吗？

提前致谢 :)

Answer 1

正如其他人指出的那样,这是一个组合优化问题的背包问题.这意味着您要查找集合的某些子集或置换,以最小化(或最大化)某个成本.另一个众所周知的问题是旅行推销员问题.

这些问题通常很难解决.但如果您对几乎最优的解决方案感兴趣,可以使用非确定性算法,如模拟退火.您很可能无法获得最佳解决方案,但几乎是最佳解决方案.

此链接解释了模拟退火如何解决背包问题,因此您应该感兴趣.

Answer 2

只是为了好玩，我尝试了准确的动态规划解决方案。用 Python 编写，因为我非常相信你不应该优化，直到你必须;-)

这可以提供一个开始，或者提供一个粗略的想法，即在诉诸近似值之前您可以得到多接近。

基于http://en.wikipedia.org/wiki/Knapsack_problem#0-1_knapsack_problem 的代码，因此信息量不足的变量名称m, W, w, v。

#!/usr/bin/python

import sys

solcount = 0

class Solution(object):
    def __init__(self, items):
        object.__init__(self)
        #self.items = items
        self.value = sum(items)
        global solcount
        solcount += 1
    def __str__(self):
        #return str(self.items) + ' = ' + str(self.value)
        return ' = ' + str(self.value)

m = {}

def compute(v, w):
    coord = (len(v),w)
    if coord in m:
        return m[coord]
    if len(v) == 0 or w == 0:
        m[coord] = Solution([])
        return m[coord]
    newvalue = v[0]
    newarray = v[1:]
    notused = compute(newarray, w)
    if newvalue > w:
        m[coord] = notused
        return notused
    # used = Solution(compute(newarray, w - newvalue).items + [newvalue])
    used = Solution([compute(newarray, w - newvalue).value] + [newvalue])
    best = notused if notused.value >= used.value else used
    m[coord] = best
    return best

def main():
    v = [int(l) for l in open('filesizes.txt')]
    W = int(sys.argv[1])
    print len(v), "items, limit is", W
    print compute(v, W)
    print solcount, "solutions computed"

if __name__ == '__main__':
    main()

为简单起见，我只考虑文件大小：一旦您有了要使用的大小列表，您就可以通过搜索列表找到一些具有这些大小的文件名，因此没有必要在核心中纠结文件名，慢程序的一部分。我还以块大小的倍数表示所有内容。

如您所见，我已经注释掉了提供实际解决方案的代码（与解决方案的价值相反）。那是为了节省内存 - 存储所用文件列表的正确方法不是每个解决方案中的一个列表，而是让每个解决方案指向它派生自的解决方案。然后，您可以通过返回链来计算最后的文件大小列表，输出每个步骤的值之间的差异。

使用 2000-6000 范围内的 100 个随机生成的文件大小的列表（我假设有 2k 个块，所以这是大小为 4-12MB 的文件），这在我的笔记本电脑上在 100 秒内解决了 W=40K。在这样做时，它计算了可能的 4M 解决方案中的 2.6M。

复杂度为 O(W*n)，其中 n 是文件数。这与问题是 NP 完全的这一事实并不矛盾。所以我至少正在接近一个解决方案，这只是在未优化的 Python 中。

显然现在需要进行一些优化，因为实际上它需要解决 W=4M（8GB DVD）以及您拥有的文件数量（比如说几千个）。假设允许该程序花费 15 分钟（与刻录 DVD 所需的时间相当），这意味着当前的性能大约减少了 10^3 倍。因此，我们遇到了一个很难在 PC 上快速准确地解决的问题，但还没有超出技术范围。

内存使用是主要问题，因为一旦我们开始点击交换，我们就会变慢，如果我们用完虚拟地址空间，我们就会遇到真正的麻烦，因为我们必须在磁盘上实现我们自己的解决方案存储。我的测试运行峰值为 600MB。如果您在 32 位机器上用 C 编写代码，则每个“解决方案”的大小固定为 8 个字节。因此，您可以生成大量的二维数组，而无需在循环中进行任何内存分配，但在 2GB 的 RAM 中，您只能处理 W=4M 和 n=67。糟糕 - DVD 已售罄。它几乎可以解决 2-k 块大小的 CD，但是：W=350k 给出 n=766。

编辑：MAK 建议自底向上迭代计算，而不是递归自顶向下计算，应该会大大减少内存需求。首先计算所有 0 <= w <= W 的 m(1,w)。从这个数组，你可以计算所有 0 <= w <= W 的 m(2,w)。然后你可以扔掉所有的 m( 1,w) 值：您不需要它们来计算 m(3,w) 等。

顺便说一句，我怀疑实际上您要解决的问题可能是装箱问题，而不仅仅是如何尽可能接近填充 DVD 的问题。也就是说，如果您有一堆文件，您希望将它们全部写入 DVD，尽可能少地使用 DVD。有些情况下，解决装箱问题很容易，但解决这个问题却很难。例如，假设您有 8GB 的​​磁盘和 15GB 的小文件。需要进行一些搜索才能找到最接近 8GB 的​​可能匹配项，但是只需将大约一半的文件放在每个磁盘上，就可以轻松解决装箱问题 - 确切地如何划分它们并不重要，因为您是无论你做什么，都会浪费 1GB 的空间。

综上所述，有极快的启发式方法可以在大部分时间提供不错的结果。最简单的是浏览文件列表（可能按大小递减顺序），如果适合，则包含每个文件，否则将其排除。如果快速近似解决方案“不够好”，您只需要回退到任何缓慢的地方，以便您选择“足够”。

Answer 3

听起来你那里有一个难题。这个问题是众所周知的，但不存在有效的解决方案（可以吗？）。