枚举法解决0/1背包问题代码

枚举法是一种直接穷举所有可能的解策略，在0/1背包问题中，通常用于求解每个物品是否放入背包的情况。这个问题涉及到给定一组物品，每种物品都有一定的价值（w[i]）和重量（c[i]），目标是在不超过背包容量W的前提下，选择物品使得总价值最大。

以下是使用Python的一个简单枚举法解0/1背包问题的例子：

def knapsack_01(capacity, weights, values):
    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 = [5, 4, 6, 3]
values = [10, 20, 30, 15]
capacity = 8
max_value = knapsack_01(capacity, weights, values)
print(f"背包可以装下的最大价值是: {max_value}")