动态规划法求解01-背包问题代码

动态规划是一种解决优化问题的有效算法，常用于求解最优化问题，如背包问题。对于01背包问题，它是这样的：给定一组物品，每件物品有自己的重量和价值，以及一个总容量限制。目标是在不超过这个容量的情况下，选择一些物品使得总价值最大。

以下是Python中使用动态规划求解01背包问题的一个常见代码示例：

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

    # 构建动态规划表
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]

    return dp[n][capacity]

# 示例
weights = [10, 20, 30]
values = [60, 100, 120]
capacity = 50
print(knapsack(weights, values, capacity))

在这个代码中，`dp[i][w]`表示在前i个物品中，容量为w的最大价值。通过遍历每个物品，并考虑包括当前物品和不包括当前物品这两种情况，动态规划表记录了所有可能的选择组合。