01背包 python

下面是Python实现的01背包问题：

def knapsack(wt, val, W, n):
    # 创建 dp 数组
    dp = [[0 for x in range(W + 1)] for y in range(n + 1)]

    # 填充 dp 数组
    for i in range(n + 1):
        for j in range(W + 1):
            if i == 0 or j == 0:
                dp[i][j] = 0
            elif wt[i - 1] <= j:
                dp[i][j] = max(val[i - 1] + dp[i - 1][j - wt[i - 1]], dp[i - 1][j])
            else:
                dp[i][j] = dp[i - 1][j]

    # 返回最大价值
    return dp[n][W]

其中，`wt`是物品重量的列表，`val`是物品价值的列表，`W`是背包容量，`n`是物品数量。函数返回最大价值。