0-1背包2行如何寻找元素

Question

继教训here 我已经实现了一个工作0-1背包算法只使用两行。 其输出正确的最终值。 名包含正在被使用的每个元素的id。

def KnapSack(val, wt, n, W): 
    names = n
    n = len(n)
    mat = [[0 for i in range(W + 1)] for i in range(2)] 

    i = 0
    while i < n: 
        j = 0 

        if i % 2 == 0: 
            while j < W:
                j += 1
                if wt[i] <= j:
                    mat[1][j] = max(val[i] + mat[0][j - wt[i]], mat[0][j]) 
                else:
                    mat[1][j] = mat[0][j] 
        else: 
            while j < W: 
                j += 1
                if wt[i] <= j: 
                    mat[0][j] = max(val[i] + mat[1][j - wt[i]], mat[1][j]) 
                else: 
                    mat[0][j] = mat[1][j] 
        i += 1
    if n % 2 == 0: 
        return mat[0][W] 
    else: 
        return mat[1][W] 

在此基础上的代码，我将如何能够输出用于创建正确的背包价值的要素是什么？ 例如，在最终输出是54，我需要找到什么样的元素加在一起得到的54值。

Answer 1

就像一般的背包，你就必须跟踪您如何在DP阵列得到了这个特殊的状态。所以，在你的mat表，而不是跟踪得到的总和，我们也将跟踪构成它的元素 - 表中的每个条目现在的名字之和列表的元组。

我还注意到在你的代码使一个重要的重构的自由 - 你怎么看类似if和你的代码的样子else条款？我们可以通过我们的基础周围i % 2逻辑团结他们 - 在我的代码，这是cur。这让我们只写这个逻辑的 - 这是一个0-1背包一个相当常见的伎俩。在一般情况下，你应该避免的复制粘贴可能的情况下，因为它往往是错误的根源。如果没有，再到期，下面的代码：

def KnapSack(val, wt, n, W): 
    names = n
    n = len(n)
    mat = [[(0, []) for i in range(W + 1)] for i in range(2)] 

    i = 0
    while i < n: 
        j = 0 
        cur = i % 2

        while j < W:
            j += 1
            if wt[i] <= j:
                if val[i] + mat[cur][j - wt[i]][0] > mat[cur][j][0]:
                    mat[1 - cur][j] = (val[i] + mat[cur][j - wt[i]][0], mat[cur][j - wt[i]][1][:] + [names[i]])
                else:
                    mat[1 - cur][j] = (mat[cur][j][0], mat[cur][j][1][:])
            else:
                mat[1 - cur][j] = (mat[cur][j][0], mat[cur][j][1][:]) 

        i += 1
    if n % 2 == 0: 
        return mat[0][W] 
    else: 
        return mat[1][W] 

print(KnapSack([7, 8, 4], [3, 8, 6], ['apple', 'box', 'peach'], 10))

打印(11, ['apple', 'peach'])，由于图11是最佳值，由第一和第三元件。

注意额外的[:]将列表的副本 - 列表不深复制，这会搞乱我们的解决方案，因为我们将保持一遍又一遍变异相同的列表。

祝你学习！