用python解决0-1背包问题代码，python0-1背包代码,照做吧，幸好这个算法算1

用python解决0-1背包问题代码，python0-1背包代码,照做吧，幸好这个算法算1

照做吧，幸好这个算法算100张票子也就是10秒不到，这还是mini-itx。 下面上算法，具体算法猛击这里（http://www.oiers.cn/pack/Index.html ）和这里（http://zh.wikipedia.org/wiki/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98 ）。输入是数字列表和目标，输出是组合和误差。f[i]是目前为止，最大代价为i所能获得的最高收益，以及组合方式。numlist是二维数组，分别是代价和收益。

def resolv_dym(numlist, target):    f = [[0, []] for i in xrange(0, target + 1)]    for c, w in numlist:        for v in xrange(target, c – 1, -1):            if f[v - c][0] + w > f[v][0]:                f[v][0] = f[v - c][0] + w                f[v][1] = f[v - c][1] + [(c, w),]    return f[target][1], float(abs(target – f[target][0]))

                                当然，在这个特例里面，代价和收益相等，所以下面是真实代码。

def resolv_dym(numlist, target):    f = [[0, []] for i in xrange(0, target + 1)]    for i in numlist:        for v in xrange(target, i – 1, -1):            if f[v - i][0] + i > f[v][0]:                f[v][0] = f[v - i][0] + i                f[v][1] = f[v - i][1] + [i,]    return f[target][1], float(abs(target – f[target][0]))