动态规划法求解背包问题

动态规划法是解决背包问题的一种常用方法。下面是01背包问题的动态规划解法：

1. 状态定义：设dp[i][j]表示前i个物品放入容量为j的背包中所获得的最大价值。

2. 状态转移方程：对于第i个物品，有两种情况：

（1）不放入背包中，此时dp[i][j] = dp[i-1][j]；

（2）放入背包中，此时dp[i][j] = dp[i-1][j-w[i]] + v[i]，其中w[i]表示第i个物品的重量，v[i]表示第i个物品的价值。

综上所述，状态转移方程为：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])。

3. 边界条件：dp[j] = 0（前0个物品放入容量为j的背包中所获得的最大价值为0），dp[i] = 0（容量为0的背包中所获得的最大价值为0）。

4. 最终结果：dp[n][m]，其中n为物品的个数，m为背包的容量。

下面是Python实现01背包问题的动态规划解法：

def knapsack01(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, capacity + 1):
            if j >= weights[i - 1]:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
            else:
                dp[i][j] = dp[i - 1][j]
    return dp[n][capacity]