0/1 背包的動態規劃（0/1 knapsack DP）

你有一個最多能裝 W 單位重量的背包，以及一組 n 件物品，每件有一個重量和一個價值。每件物品要嘛整件拿走，要嘛留下——你不能拿其中一部分，故稱「0/1」。你想要在仍裝得下重量上限的前提下，選出最有價值的一批物品。這是貪婪法失敗的經典問題：按最佳價值重量比去抓物品，可能超重或浪費容量，所以你確實需要考慮各種組合，而動態規劃正是俐落的做法。

狀態是 dp[i][w] = 只用前 i 件物品、重量預算為 w 時可達的最大價值。在物品 i 處的轉移考慮兩種情況。你可以跳過物品 i，使 dp[i-1][w] 不變。或者，若物品 i 裝得下（weight[i] <= w），你可以拿它，得到 value[i] 加上「用前 i-1 件物品、預算減為 w - weight[i] 時能做到的最佳值」。所以 dp[i][w] = max( dp[i-1][w], value[i] + dp[i-1][w - weight[i]] )，基底情況為對所有 w，dp[0][w] = 0（沒有物品，沒有價值）。讓 i 從 1 到 n、w 從 0 到 W 填表，得到 O(nW) 時間與 O(nW) 空間；由於每一列只依賴前一列，你可以把一個一維陣列從高 w 往低 w 覆寫，壓縮成 O(W) 空間（往下的方向至關重要，以確保每件物品最多用一次）。

這裡有兩個誠實的警告很重要。第一，O(nW) 看似多項式，但 W 是一個用約 log W 位元寫成的數，所以執行時間相對於輸入的位元長度是指數的——這稱為偽多項式，正是為何 0/1 背包儘管有這張漂亮的表卻仍是 NP 困難：唯有 W 很小時這個演算法才高效。第二，這是貪婪法出錯的課本範例：分數背包用貪婪的比值規則可得最佳解，但 0/1 版本不行，這生動地提醒我們「拿局部最好的物品」並不是最佳性的證明。相對地，這個動態規劃透過最佳子結構是可證明正確的。