B1 實屬牛逼

這是多重背包問題

透過範例二來解釋的話你可能會比較清楚 首先妳應該知道eachp這個陣列每一個index都代表著重量 你問的那段概念簡單來說就是想要得到eachp在每一個不同的重量所能夠得到得最高價 舉例的話 i=0 j=30遞減到26 if皆會成立 然後eachp[30~26]都為64 i=1 j=30遞減到22 if皆會成立 然後eachp[30~22]都為85 i=2 j=30遞減到4 if皆會成立 然後eachp[30~26]會變成85+52 25~22 為85 21~4 為52 以此類推 妳就會了解了 加油囉 不懂的可以試著寫在紙上或是用IDE的逐步執行

B4 太謝謝你了QQ 整個白天都很灰心 謝謝你的鼓勵跟幫忙

B5 沒事的～ 一開始學難免會碰壁 妳會越來越強的！ 加油

B6 謝謝你😭😭😭😭

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 那我建議妳先看懂底下這版比較容易的解（原程式更進一步將二維陣列降至一維陣列，因為只相依於前一列）。

knapsack problem可以試著用dp來練習看看，是dp的蠻基本題