用python解决0-1背包问题代码

2022-03-11 00:00:00 python 解决

输入是数字列表和目标，输出是组合和误差。f[i]是目前为止，最大代价为i所能获得的最高收益，以及组合方式。numlist是二维数组，分别是代价和收益。

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]))

相关文章