【學習筆記】動態規劃(1)

開場

作為重要演算法之一，「動態規劃」亦曾成為APCS的考題，著名的「0-1背包問題」即是一可以使用「動態規劃」來求解的題目！

0-1背包問題

觀念

假設今天有一背包，其負重限制為max_w公斤，意即此背包最多只能戴上max_w公斤的物品。而一旁有多個重量(w)與價值(v)不等的物品，這些物品不可分割，只能選擇「取」或「不取」。我們的目標，是要在負重限制(max_w)的範圍內，帶走總價值最高的物品組合。

思路

我們可以先到這個網站，點進去後，應該會見到類似於以下的頁面

網站右邊有一個表格，黃色(w)部分表重量，綠色(v)部分表物品價值。

在上面的圖片，有兩個黃色的部分，位於表格較上方的是當前背包的負重限制(max_w)，位於左側的代表當前物品的重量(w)，如果要將物品帶入背包，則w必須<=max_w。

那麼我們接下來要做的，就是進行比較。我們先把目光放到這個表格：

注意：每次開啟頁面後的數值皆不同，請務必自行判斷，本文僅提供一大概方向。

現在的狀態是：我的背包負重限制為1，而目前我手上有一個重量5、價值5的物品。顯而易見的，我沒辦法將這個物品裝進背包，所以「?」欄（表目前背包內物品總價值）填入0，如下圖。

那麼背包的負重強度要多少才能裝下這個重量5、價值5的物品？很簡單的，那一定是負重能力>=5的背包嘛！也就是說，負重能力1~4的背包在這個階段是無法帶上物品的，所以都填入0。

接著當我們來到負重限制為5的背包時，因為其max_w>=5，符合要求，因此我們可以很放心地填入「5」

（注意！這裡填入的5指的是物品的價值，而非重量，只是剛好其價值與重量同數值！）

值得注意的是，在下面的圖可以看見兩個綠色的格子，它的意義是：當前背包最高負載重量是6，而我的物品重量是5，也就是說，我們還有6-5=1的「扣打」可以裝東西，而下方的圖，意思是：我的背包max_w==6，而物品的w==5，所以我還有1的配額可以裝東西，而這個1的配額裡，我所有的物品價值為0。

而既然max_w==5的背包可以帶上這個物品，max_w==6的當然也可以囉！所以max_w==6的背包也可以放心填入「5」囉！

接著我們來到了下一段，現在我們要帶的物品重量5、價值2

那麼接下來的規則也很簡單，只要遵循以下規則即可：

1. 確認物品重量w是否>=當前背包的max_w
2. 如果不是，則將該格正上方1格（即藍色格）的數值填入；如果是，則接續第3步驟
3. 檢查綠色格的數值是否>藍色格的內容，如果是，則填入綠色格的數值之和；否則填入藍色格的數值。

之後依此類推。

如此一來，便可完成這張表格了，最後，最右下角的值即為所求！

結語

今天簡單帶入動態規劃在1-0背包問題的應用觀念，下一篇開始帶相關的程式碼！
希望這篇文章對您有所幫助囉 :D