algorithm - 寻找最佳的文件大小组合

Question

这是一个问题，我想已经有一种算法了-但我似乎不知道与google搭配使用的正确词:)。

问题:我想编写一个小程序，选择包含任何文件的目录(但出于我的目的，媒体文件，音频和视频)。之后，我要输入以MB为单位的最大总文件大小总和，不能超过该总和。此时，您将点击“计算最佳拟合”按钮。

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

这样，您可以找出刻录CD或DVD时要合并的文件，从而可以尽可能多地使用该光盘。

我已经尝试为此提出一种算法-但失败了:(。

有人知道一些不错的算法可以做到这一点吗？

提前致谢 :)

Answer 1

只是为了好玩，我尝试了准确的动态编程解决方案。用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()

为简单起见，我只考虑文件大小:一旦有了要使用的大小列表，便可以通过搜索列表来找到具有这些大小的文件名，因此毫无意义地将文件名混在内核中，速度很慢该程序的一部分。我还用块大小的倍数表示所有内容。

如您所见，我已经注释掉了给出实际解决方案的代码(而不是解决方案的值(value))。那是为了节省内存-存储使用的文件列表的正确方法不是每个解决方案中的一个列表，而是使每个解决方案都指向其来源的解决方案。然后，您可以返回链，最后计算文件大小列表，并在每个步骤输出值之间的差异。

列出了100个随机生成的文件，大小在2000-6000之间(假设2k块，因此文件大小为4-12MB)，这可以在我的笔记本电脑上100秒内解决W = 40K。这样做可以计算出2.6M可能的4M解决方案。

复杂度为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)等。

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

综上所述，非常快的启发式方法在很多时候都能提供不错的结果。最简单的方法是遍历文件列表(可能以大小减小的顺序)，并在适合的情况下包括每个文件，否则将其排除。如果您选择的“足够多”的快速近似解决方案还不够“好”，那么您只需回到慢速运行。