《靈珠覺醒：從零到算法金仙的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>>