《灵珠觉醒：从零到算法金仙的C++修炼》卷三·天劫试炼（34）混元金斗装万物 - 0-1背包问题（二维DP）

《灵珠觉醒：从零到算法金仙的C++修炼》卷三·天劫试炼（34）混元金斗装万物 - 0-1背包问题（二维DP）

哪吒在数据修仙界中继续他的修炼之旅。这一次，他来到了一片神秘的混元谷，谷中有一座巨大的混元金斗，斗身闪烁着神秘的光芒。谷口有一块巨大的石碑，上面刻着一行文字：“欲破此谷，需以混元金斗之力，装万物，二维DP显真身。”

哪吒定睛一看，石碑上还有一行小字：“物品列表[[2, 3], [3, 4], [4, 5]]（重量，价值），背包容量为5，最大价值为7。”哪吒心中一动，他知道这是一道关于0-1背包问题的难题，需要通过二维动态规划的方法，在不超出背包容量的前提下，找到能装入背包的最大价值物品组合。

暴力解法：混元金斗的初次尝试

哪吒心想：“要解决0-1背包问题，我可以尝试所有可能的物品组合。”他催动混元金斗之力，通过递归的方式，枚举所有可能的物品组合，计算每种组合的总价值和总重量，记录最大价值。

int knapsack(vector<vector<int>>& items, int capacity) {
   
    return knapsackHelper(items, capacity, 0);
}

int knapsackHelper(vector<vector<int>>& items, int capacity, int index) {
   
    if (index >= items.size() || capacity <= 0) return 0;
    int value = knapsackHelper(items, capacity, index + 1); // 不选当前物品
    if (capacity >= items[index][0]) {
    // 选当前物品
        value = max(value, items[index][1] + knapsackHelper(items, capacity - items[index][0], index + 1));
    }
    return value;
}

哪吒成功地计算了最大价值，但混元金斗的光芒却黯淡了下来。他意识到，这种方法虽然可行，但时间复杂度极高，尤其是当物品数量很多时，灵力消耗巨大。

C++语法点

在C++中，二维动态规划是解决0-1背包问题的常用方法。以下是一些重要特性：

• 二维数组：

  • 使用vector<vector<int>>表示动态规划表。
  • 常用操作：
    • dp[i][j]：访问第i个物品、容量为j时的最大价值。
    • 初始化二维数组：vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0))。

• 动态规划：

  • 通过状态转移方程dp[i][j] = max(dp[i-1][j], dp[i-1][j - weight] + value)计算当前状态的最大价值。

高阶优化：二维DP的智慧

哪吒元神中突然浮现金色铭文——「混元金斗装万物，二维DP显真身」。他意识到，可以通过二维动态规划的方法，优化0-1背包问题的解决过程。

哪吒决定使用二维动态规划，创建一个二维数组dp，其中dp[i][j]表示前i个物品在容量为j时的最大价值。通过状态转移方程，他成功地计算了最大价值，而且灵力消耗大幅减少。

int knapsack(vector<vector<int>>& items, int capacity) {
   
    int n = items.size();
    vector<vector<int>>