0/1 Knapsack Problem – Top-Down DP Approach (recursion with memoization) 給定一個大小為 N 的背包以及 M 個物件，每個物件皆有固定的大小與價值，問挑選哪些物件能獲得最大收益？ 例，背包大小為 3，物件共有 3 個，其大小與價值如下所示：

接下來有兩種可能，一是將物件 1 挑選進入背包裡，這樣可以獲得價值 4，但同時也會讓背包的空間變小，背包的空間變小就有可能會裝不下後續的物件，因此，第二種可能便是跳過不選這個物件，保持背包的容量來裝後續的物件。 這是一個很簡單的範例，所以我們可以很輕鬆地發現到，最大的收益會是 5，也就是將物件 2, 3 選入袋中，而不選物件 1。 至此，我們的遞迴關係式 (recurrence/transition function) 已經有苗頭了，這是解動態規劃問題最關鍵的一步。

(1): 不選這個物件，所以背包的大小維持不變。 (2): 選取這個物件，獲得了物件的價值 (+ item.price)，但失去了背包的容量 (- item.size)。 因為我們要最大收益，所以回傳 (1), (2) 值較大者。 最後，別忘了遞迴關係式需要 base case，否則會陷入無限遞迴，base case 通常都很直覺： 1. 背包的大小為零，表示沒有空間可以放任何物件了。 2. 這是最後一個物件了，已經沒有下一個物件了。

關於 bottom-up DP 我就不細講了，因為兩者的差別僅在於空間複雜度（遞迴需要額外的堆疊空間），但時間複雜度是一樣的，且 top-down 也比較容易理解，通常在解動態規劃的問題時都是先從 top-down 開始下手，找出原問題與子問題之間的關係 (recurrence/transition function)，之後有時間才會做 bottom-up 改善空間複雜度，不過在打程式競賽的時候，妳通常不會有這麽多時間，能拿到 accepted 就緊接著寫下一題了，因為妳花得時間越少名次也就越高，假如妳真的很想搞懂 bottom-up DP 那我建議妳先看懂底下這版比較容易的解（原程式更進一步將二維陣列降至一維陣列，因為只相依於前一列）。