背包问题python

背包问题是一个经典的动态规划问题，在Python中也可以用动态规划算法来解决。

下面是一个示例代码，它使用了动态规划算法来解决0/1背包问题：

def knapsack(W, wt, val, n):
    # 初始化dp数组
    dp = [[0 for x in range(W+1)] for x 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)

print(knapsack(W, wt, val, n))

这个代码实现了一个函数`knapsack`，它接受四个参数：背包的容量`W`，物品的重量`wt`，物品的价值`val`和物品的数量`n`。函数返回最优解，即在不超过背包容量的情况下可以获得的最大价值。

在这个示例中，我们定义了三个物品，它们的重量分别是10、20和30，价值分别是60、100和120。背包的容量是50，我们要在这个背包中装入物品，使得装入的物品价值最大。

运行这个代码，输出结果为220，表示在装入物品的总重量不超过50的情况下，可以获得的最大价值是220。