动态规划算法求01背包

01背包问题是一个经典的动态规划问题。给定一个背包容量和一些物品，每个物品有一个重量和一个价值。要求选出若干个物品放入背包中，使得背包中物品的总重量不超过背包容量，且背包中物品的总价值最大。

可以用一个二维数组 dp[i][j] 表示前 i 个物品，背包容量为 j 时的最大价值。则状态转移方程如下：

当 j < w[i] 时，dp[i][j] = dp[i-1][j] （当前物品无法放入背包中）
当 j >= w[i] 时，dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) （当前物品可以放入背包中，取放入和不放入的最大值）

最终的最大价值即为 dp[n][W]，其中 n 为物品数量，W 为背包容量。

下面是 Python 代码实现：

def knapsack(W, wt, val, n):
    dp = [[0 for _ in range(W+1)] for _ in range(n+1)]
    
    for i in range(1, n+1):
        for j in range(1, W+1):
            if j < wt[i-1]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-wt[i-1]] + val[i-1])
    
    return dp[n][W]

其中，W 是背包容量，wt 和 val 分别是物品的重量和价值，n 是物品数量。