如何在使用递归动态规划时填充背包表格

Question

如何在使用递归动态规划时填充背包表格

pythonrecursiondynamic-programmingknapsack-problembottom-up

5

*不是作业*

我在Python中实现了背包问题，并成功地获得了最佳价值，但我想将问题扩展到填充包含所有重量和物品的背包表的所有适当值。

我已经在Python中实现了它，但我对此语言还很陌生，请告诉我是否有任何可以改进的地方，然而这些概念应该在任何语言中都能够工作。

values, weights, table = [], [], [[]]

def knapsack(i, W):
    global weights, values, table, counter
    if (i < 0):
        # Base case
        return 0
    if (weights[i] > W):
        # Recursion
        return knapsack(i - 1, W)
    else:
        # Recursion
        return max(knapsack(i - 1, W), values[i] + knapsack(i - 1, W - weights[i]))

def main():
    global values, weights, table
    W = int(input())
    values = list(map(int, input().split()))
    weights = list(map(int, input().split()))
    # initalise table with 0's
    table = [[0 for i in range(W)] for i in range(len(values))]
    for i in range(len(values)):
        for j in range(W):
            table[i][j] = 0
    # Fill table
    print("Result: {}".format(knapsack(len(values) - 1, W)))
    printKnapsack(W)

if __name__ == '__main__':
    main()

我还有一个打印表格的方法，虽然与此无关，但您可以看到我的输出内容：

我也有这个打印表格的方法，虽然与此无关，但是您可以看到我输出的内容：

def printLine(W):
    print(" ",end="")
    for i in range(W + 1):
        print("-----",end="")
    print("")

def printKnapsack(W):
    global table
    print("\nKnapsack Table:")
    printLine(W)
    print("| k\w |", end="")
    for i in range(W):
        print("{0: >3} |".format(i + 1), end="")
    print("")
    printLine(W)
    for i in range(len(values)):
        print("|  {}  |".format(i+1), end="")
        for j in range(W):
            print("{0: >3} |".format(table[i][j]), end="")
        print("")
        printLine(W)

这是示例输入：

10
18 9 12 25
5 2 4 6

这是应该输出的内容：

Result: 37

Knapsack Table:
 -------------------------------------------------------
| k\w |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 | 10 |
 -------------------------------------------------------
|  1  |  0 |  0 |  0 |  0 | 18 | 18 | 18 | 18 | 18 | 18 |
 -------------------------------------------------------
|  2  |  0 |  9 |  9 |  9 | 18 | 18 | 27 | 27 | 27 | 27 |
 -------------------------------------------------------
|  3  |  0 |  9 |  9 | 12 | 18 | 21 | 27 | 27 | 30 | 30 |
 -------------------------------------------------------
|  4  |  0 |  9 |  9 | 12 | 18 | 25 | 27 | 34 | 34 | 37 |
 -------------------------------------------------------

我已经尝试了多个不同的方法在knapsack(i, W)函数中添加元素到表格中，我也画出来了但是我还是不能理解递归是如何工作的，无法确定应该添加哪些索引值以加入递归调用的展开值。

这是我需要修复的方法。

def knapsack(i, W):
    global weights, values, table, counter
    if (i < 0):
        # Base case
        return 0
    if (weights[i] > W):
        # Recursion
        table[?][?] = ?
        return knapsack(i - 1, W)
    else:
        # Recursion
        table[?][?] = ?
        return max(knapsack(i - 1, W), values[i] + knapsack(i - 1, W - weights[i]))

- joshuatvernon

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- A. Chubarov · Accepted Answer

在您的递归算法中，您无法获得完整的填充表，因为此步骤会跳过很多内容：

return max(knapsack(i - 1, W), values[i] + knapsack(i - 1, W - weights[i]))

我可以建议您使用这个解决方案：

def knapsack(i, W):
    global weights, values, table, counter
    if (i < 0):
        # Base case
        return 0
    if (weights[i] > W):
        # Recursion
        table[i][W-1] = knapsack(i - 1, W)
    else:
        # Recursion
        table[i][W-1] = max(knapsack(i - 1, W), values[i] + knapsack(i - 1, W - weights[i]))
    return table[i][W-1]

在结果表中，非零单元格表示您的算法在此步骤通过并获得了这个中间解。此外，您可以多次运行算法，并使用不同的输入值来完成整个表格。

希望这有所帮助。