如何从背包DP矩阵求出所有解

Question

我正在研究背包问题的DP解决方案。有了一个项目及其权重和价值的列表，我需要找到项目的最大总价值小于一些预定义的权重。没什么特别的，只是0-1 knapsack。在

我使用DP生成矩阵：

def getKnapsackTable(items, limit):
    matrix = [[0 for w in range(limit + 1)] for j in xrange(len(items) + 1)]
    for j in xrange(1, len(items) + 1):
        item, wt, val = items[j-1]
        for w in xrange(1, limit + 1):
            if wt > w:
                matrix[j][w] = matrix[j-1][w]
            else:
                matrix[j][w] = max(matrix[j-1][w], matrix[j-1][w-wt] + val)

    return matrix

其中items是元组的列表(name, weight, value)。现在有了DP矩阵，最大可能值是右下位置的数字。我也可以回溯矩阵，找到给出最佳解决方案的项目列表。在

^{pr2}$

很好，现在我可以得到结果：

items = [('first', 1, 1), ('second', 3, 8), ('third', 2, 5), ('forth', 1, 1), ('fifth', 1, 2), ('sixth', 5, 9)]
matrix = getKnapsackTable(items, 7)
print getItems(matrix, items)

并将看到：[('fifth', 1, 2), ('third', 2, 5), ('second', 3, 8), ('first', 1, 1)]。在

---

问题是这不是唯一的解决方案。代替'first'元素，我可以采用'forth'元素（这是绝对相同的，但有时解决方案可能不同）。我正在想办法找到所有的解决办法，而不是只有一个。我知道这需要更多的时间，但我同意。在

Answer 1

您可以像往常一样计算原始的DP矩阵（即使用DP），但是要找到所有的最优解，您需要在从最终状态返回矩阵时递归。这是因为矩阵中任何给定的状态（i，j）至少有一个最优的前置状态，但它可能有两个：状态（i-1，j-w（i））的最优解中添加项i，可以达到状态（i，j）的最大值，或者不考虑第i项，只保留（i-1，j）的最优解。当这两个选择的总价值相等时，即

matrix[i-1][j] == matrix[i-1][j-w(i)]+v(i),

其中w（i）和v（i）分别是对象i的重量和值。每当您检测到这样的分支时，您需要跟踪每个分支。在

注意，可能存在大量的最优解：例如，考虑当所有项目的权重为1时的情况。在这种情况下，所有（n-choose-w）解都是最优的。在