用动态规划算法求解01背包问题python代码

下面是使用动态规划算法求解01背包问题的Python代码：

def knapsack_dp(values, weights, capacity):
    n = len(values)
    # 创建一个二维数组dp作为动态规划表，dp[i][j]表示前i个物品放入容量为j的背包中所能获得的最大价值
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, capacity + 1):
            if weights[i - 1] > j:
                # 背包容量不足，无法放入第i个物品
                dp[i][j] = dp[i - 1][j]
            else:
                # 可以选择放入第i个物品或者不放入第i个物品，取较大值
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
    return dp[n][capacity]

其中，values是一个长度为n的列表，表示每个物品的价值；weights也是一个长度为n的列表，表示每个物品的重量；capacity是背包的容量。函数返回可以放入背包的最大价值。