用python解决背包问题

在Python中，背包问题是一个经典的动态规划问题，通常用于资源分配场景，例如物品选择的问题。有两个常见的版本：0-1背包问题和完全背包问题。

1. **0-1背包问题**：
- 定义：给定一组物品，每个物品有自己的重量w[i]和价值v[i]，有一个总重量W的背包，问如何选择物品使得背包中物品的总价值最大。
- 动态规划解决方案：
- 使用二维数组dp，其中dp[i][j]表示前i件物品放在容量为j的背包中能得到的最大价值。
- 从最小物品开始遍历，对于每个物品，有两种选择：放入背包或不放。如果放入，则更新dp值；如果不放，则dp值不变。

2. **完全背包问题**（允许无限次取某个物品）：
- 解决方法类似，只是在计算dp值时，可以选择多次包含同一件物品。

以下是简单的Python代码示例（以0-1背包为例）：

def knapsack(W, wt, val, n):
    dp = [[0 for w in range(W + 1)] for i in range(n + 1)]
    
    # 构建动态规划表
    for i in range(1, n + 1):
        for w in range(1, W + 1):
            if wt[i - 1] <= w:
                dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w])
            else:
                dp[i][w] = dp[i - 1][w]
                
    return dp[n][W]

# 示例输入
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
max_value = knapsack(W, wt, val, n)

print(f"最大价值为 {max_value}")