经典动态规划：0-1 背包问题

经典动态规划：0-1 背包问题

问题描述

给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i]，价值为 val[i]，现在让你用这个背包装物品，最多能装的价值是多少？

举例：

输入：

N = 3, W = 4
wt = [2, 1, 3]
val = [4, 2, 3]

输出：

6

解释：选择前两件物品装进背包，总重量 3 小于 W，可以获得最大价值 6。

解题思路

0-1 背包问题是一个典型的动态规划问题，其核心在于 穷举所有可能的装包方案，并找到价值最大的方案。由于物品不可分割，每个物品只有 "装入背包" 和 "不装入背包" 两种状态，因此被称为 0-1 背包问题。

解决此类问题，通常采用以下步骤：

1. 确定状态和选择

• 状态： 描述问题局面，需要考虑背包容量和可选择的物品，因此状态有两个：背包容量 w 和 可选择的物品范围 i。
• 选择： 对于每个物品，可以选择 "装入背包" 或 "不装入背包"。

2. 定义 dp 数组

根据状态，定义一个二维 dp 数组：

• dp[i][w] 表示：对于前 i 个物品，当前背包的容量为 w 时，可以装下的最大价值。

最终目标是求解 dp[N][W]，即考虑所有物品，背包容量为 W 时的最大价值。

3. 推导状态转移方程

根据选择的两种情况，推导状态转移方程：

• 不装入第 i 个物品： dp[i][w] = dp[i-1][w]，最大价值继承之前的状态。
• 装入第 i 个物品： dp[i][w] = dp[i-1][w - wt[i-1]] + val[i-1]，即在剩余重量 w - wt[i-1] 限制下寻求最大价值，并加上当前物品的价值。

最终状态转移方程为：

dp[i][w] = max(dp[i-1][w], dp[i-1][w - wt[i-1]] + val[i-1]) 

4. 处理边界情况

• 当没有物品或背包没有空间时，最大价值为 0，即 dp[0][..] = dp[..][0] = 0。
• 需要处理 w - wt[i-1] < 0 的情况，此时无法装入第 i 个物品，只能选择不装入。

代码实现 (C++)

int knapsack(int W, int N, vector<int>& wt, vector<int>& val) {
    // 初始化 dp 数组
    vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));
    // 状态转移
    for (int i = 1; i <= N; i++) {
        for (int w = 1; w <= W; w++) {
            if (w - wt[i-1] < 0) {
                // 无法装入第 i 个物品
                dp[i][w] = dp[i - 1][w];
            } else {
                // 择优：装入或不装入
                dp[i][w] = max(dp[i - 1][w - wt[i-1]] + val[i-1], 
                               dp[i - 1][w]);
            }
        }
    }
    return dp[N][W];
}

总结

0-1 背包问题是动态规划的入门问题，其状态转移方程相对容易理解。掌握此类问题的解题思路，对于解决其他动态规划问题也大有裨益。