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

Question

我正在研究背包问题的DP解决方案。有了一个包含重量和价值的物品列表，我需要找到最大总价值小于某个预定义重量的物品。没什么特别的，就是0-1个背包。

我使用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 矩阵，最大可能值就是右下位置的数字。我还可以回溯矩阵以找到提供最佳解决方案的项目列表。

def getItems(matrix, items):
    result = []
    I, j = len(matrix) - 1, len(matrix[0]) - 1
    for i in range(I, 0, -1):
        if matrix[i][j] != matrix[i-1][j]:
            item, weight, value = items[i - 1]
            result.append(items[i - 1])
            j -= weight

    return result

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

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, j) 的最大值可能可以通过选择添加项来实现i 为状态 (i-1, jw(i)) 的最优解，或者将项目 i 排除在外并仅保留 (i-1, j) 的最优解。当这两个选择产生相等的总值时，即发生这种情况

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

其中 w(i) 和 v(i) 分别是物体 i 的重量和价值。每当你检测到这样的分支时，你就需要跟踪每个分支。

请注意，可能存在极其大量的最佳解决方案：例如，考虑所有项目的权重为 1 的情况。在这种情况下，所有（n 选择 w）解决方案都是最佳的。