动态规划求解背包问题

动态规划（Dynamic Programming, DP）是一种通过将复杂问题分解为更简单的子问题来解决问题的方法。背包问题（Knapsack Problem）是动态规划的经典应用之一。背包问题通常分为两种：0-1背包问题和完全背包问题。这里我们主要介绍0-1背包问题的动态规划解法。

### 0-1背包问题描述
给定一组物品，每个物品有一个重量和一个价值，在限定的总重量内，如何选择物品使得总价值最大。

### 动态规划解法
假设有n个物品，背包的容量为W。第i个物品的重量为w[i]，价值为v[i]。我们定义一个二维数组dp[i][j]，表示前i个物品在背包容量为j的情况下可以获得的最大价值。

#### 状态转移方程
1. 如果不选择第i个物品，那么dp[i][j] = dp[i-1][j]。
2. 如果选择第i个物品，那么dp[i][j] = dp[i-1][j-w[i]] + v[i]。

因此，状态转移方程为：
\[ dp[i][j] = \max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]) \]

#### 初始化
dp[0][j] = 0，表示没有任何物品时，最大价值为0。
dp[i][0] = 0，表示背包容量为0时，最大价值为0。

#### 伪代码

for i from 1 to n:
    for j from 1 to W:
        if j >= w[i]:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
        else:
            dp[i][j] = dp[i-1][j]

#### 空间优化
由于dp[i][j]只依赖于dp[i-1][j]和dp[i-1][j-w[i]]，我们可以使用一维数组来优化空间复杂度。

for i from 1 to n:
    for j from W downto w[i]:
        dp[j] = max(dp[j], dp[j-w[i]] + v[i])

### 完整示例
假设有3个物品，重量分别为2, 3, 4，价值分别为3, 4, 5，背包容量为5。

物品编号    重量    价值
1           2       3
2           3       4
3           4       5

初始化：
dp = [0, 0, 0, 0, 0, 0]

第一次迭代：
dp = [0, 0, 3, 3, 3, 3]

第二次迭代：
dp = [0, 0, 3, 4, 4, 7]

第三次迭代：
dp = [0, 0, 3, 4, 5, 7]

最终结果：
最大价值为7