動態規劃入門——多重揹包與單調優化

今天是算法與數據結構的第14篇文章，也是動態規劃專題的第三篇。

在之前的文章當中，我們介紹了多重揹包的二進制拆分的解法。在大多數情況下，這種解法已經足夠了，但是如果碰到極端的出題人可能還是會被卡時間。這個時候只能用更加快速的方法，也就是今天我們要一起來看的單調優化。

單調優化是單調隊列優化的簡稱，單調棧我們在之前的LeetCode專題已經介紹過了。它的本質只是一個簡單的棧，通過在插入元素時候對棧頂的部分元素進行彈出，從而保證了棧內元素的有序。而單調隊列也類似，只是插入元素的位置不同而已。棧是隻能從棧頂插入，隊列則是從隊尾插入。

比如我們看下下圖，下圖就是一個典型的單調隊列，隊列中的元素是[10, 6, 3]。隊首是10，隊列當中的元素從隊首開始往隊尾遞減。

如果這個時候我們從隊尾插入9，由於9大於隊尾的3，所以3出隊列，我們繼續判斷，發現9依然大於6，所以6再次出隊列。最後得到的結果是[10, 9]。準確的說，由於我們進出隊列的操作可以同時在隊首或者隊尾進行，所以嚴格說起來這並不是普通的隊列，而是一個雙端隊列。

單調隊列或者說單調棧的最大用處是由於容器內元素遞增或者遞減，所以棧頂或者是隊首的元素就是最值。我們通過使用單調棧可以在常數時間內獲得某一個區間內的若干個最值，在一些問題當中只獲得一次最值還是不夠的。因為種種條件的限制，所以可能使得最值不一定能夠成立，這個時候需要求第二最值或者是第三最值，在這種問題下， 使用單調棧或者是單調隊列就是非常有必要的了。

比如今天要討論的多重揹包問題，就是這樣的情況。

基礎分析

我們先把單調隊列的事情先放在一邊，先來仔細分析一下題目。

在之前的文章當中，我們曾經討論過動態規劃算法的複雜度問題。對於動態規劃算法而言，我們要做的是遍歷所有的決策，以及決策可以應用的狀態，找到每個狀態最佳的轉移，記錄這些最好的轉移結果。在所有的結果當中的最值，就是我們要找的整個問題的答案。那麼，我們可以很方便地推導出動態規劃的複雜度，等於狀態數乘上決策數。

我們記住這個簡單的結論，它可以幫助我們很方便地分析動態規劃算法的複雜度，尤其在一些通過傳統方法不方便分析的時候。

我們把複雜度結論帶入多重揹包問題，對於多重揹包問題來說，我們的決策是由兩個條件決定的。其中一個是物品，另一個是這個物品的數量。所以決策的數量等於物品數乘上物品的個數，狀態是揹包的容量。我們假設物品的數量是N，物品的個數為M，揹包的容量是V，那麼它的複雜度就是O(NVM)。顯然，在絕大多數情況下，這個複雜度是我們不能接受的，也是我們需要引入種種優化的原因。

在之前的文章當中，我們通過二進制表示法，將物品的數量拆分成了若干個2次冪的和。所以對於二進制表示法而言，它的複雜度是 O(NVlogM)。我們通過二進制表示將M這一維降到了logM，那麼有沒有辦法將它繼續簡化呢？

當然是有的，我們繼續來分析。在NVM這三個維度當中，N是無論如何不能減少的。我們有N種物品再怎麼樣也得比較一下這N個物品的好壞優劣，不可能說還有策略都不考慮就得到最優結果，這是不可能的。既然N這一維度不能動，我們只能從VM這兩個維度入手了。

這個M比較討厭，我們能不能想一個辦法來解決掉它呢？

在樸素的想法當中，我們需要遍歷拿取的個數來找到最優的子結構。比如當前的狀態是i，我們需要遍歷0-M中所有的j，看看究竟dp[i]的最優解是通過哪一個j轉移得到的。那麼有沒有辦法，我們不用枚舉，自動可以獲取呢？

當然是有的，這個也是單調隊列優化的精髓。

單調隊列

下面，我們來一點一點推導單調優化的過程。

首先，我們假設當前遍歷到的狀態是i，也就是揹包容量是i，當前的物品是item，它的體積是v，價值是p，數量是n。我們先來看第一個洞見，對於狀態i而言，它只能從i-kv狀態轉移得到。這裡的k是一個[0, min(i / v, n)]範圍內的整數，min(i / v, n)這個式子我想應該大家都能看懂，就是當前狀態i最多能夠包含多少個物品item。這個數量是物品數量的上限n和i這個狀態最多裝得下的數量i / v中較小的那個，我們令min(i / v, n)這個值叫做cnt。

也就是說對於狀態i而言，它最多包含cnt個item，最少包含0個。那麼它的轉移可能性一共只有cnt種，而不可能從i-1以及i-2等其他狀態轉移到。我們寫出這個狀態轉移方程，可以得到：

也就是說在當前item也就是當前決策下，狀態i的最好結果一定是由一系列確定的子狀態其中之一轉移得到的，並且這些子狀態和一個整數k掛鉤，k的取值範圍是[0, cnt]。我們先暫時忽略這個範圍，簡化問題。考慮最極端的情況，最極端的情況這個物品數量管夠，在這種情況下，我們可以列一下可以通過item轉移到i的所有狀態，它是一個序列：[i % v, i % v + v, i % v + 2v, ..., i - v]。

在之前裸的做法當中，我們是通過一重循環來遍歷了這個序列，從其中找到了最佳的轉移。我們現在希望可以不用遍歷，通過某種方法快速找到其中最優的狀態進行轉移。這個邏輯應該不難理解，到這裡，我們沒有引入任何花哨的操作。

我們下面來做一點簡單的分析，我們已經列舉出了對於狀態i所有可能轉移到的上游狀態。我們不希望通過遍歷來找到其中最佳的轉移，順著這個思路，我們大概可以猜測一下，應該通過某種方法找到這個序列當中的某個最值。只有這樣，我們才可以不需要遍歷，快速找到答案。但是通過什麼方法，尋找什麼最值我們現在還不知道。到這裡，我們又往前進了一步，大概知道了接下來的策略，但是具體的細節我們還不知道，沒關係，我們先放一放，繼續進行分析。

為了簡化書寫，我們

我們當然希望可以簡單地從dp[m], dp[m+v], dp[m+2v]...dp[i-v]這個序列當中選取最大的那個，但是由於上面這個結論，所以我們並不能這麼做。不能這麼做的原因有兩個，一個剛才說了，因為dp[i]是一個隨著i遞增而遞增的序列，揹包裝的東西越多，裝的價值只會越大，不會減少。還有一個原因是後效性，這個問題和零一揹包的情況有些相似。舉個例子，比如說dp[m] = x，如果dp[m+v]=x+p，也就是說dp[m+v]由dp[m]轉移得到，代表它已經裝了一個物品item。如果我們再從dp[m+v]進行轉移，我們則無法判斷到底一共拿取了多少個物品，也就無法判斷是否違法。

這兩個問題，我們一個一個來解決，先說第二個問題。這個問題解決的方法很多，最簡單的就是將這個序列的結果單獨存儲一份，使得當我們更新dp的時候不會影響。在零一揹包當中我們通過倒敘遍歷來解決了這個問題，但是在多重揹包當中，這種方法不太適用。接著我們來看第一個問題，我們直接找到序列最值不可行的原因是因為揹包容量引起了不公，為了解決問題，我們需要想辦法消除這種不公。消除的辦法也簡單，我們可以通過某種方法，將這些值放到同一個基準，消除因為容量變化引起的不公。

實際上這個基準很好找，就是m。我們假設dp[m], dp[m+v], dp[m+2v]...dp[i-v]這個序列當中的值都是通過dp[m]轉移得到的。比如dp[m+v]，如果是從dp[m]轉移得到的，那麼dp[m+v]應該等於dp[m]+p。同理，dp[m+2v]應該等於dp[m]+2p。這裡需要注意，這裡的數據都是沒有經過item物品更新過的結果，是上一個物品更新之後得到的值。所以這裡的dp[m+v]一定不是通過dp[m]轉移得到的，如果dp[m+v] - p > dp[m]，那麼顯然可以說明dp[m+v]的潛力要比dp[m]更大，因為同樣的體積v，它創造了更多價值。同理，如果dp[m+2v] - 2p > dp[m+v] - p，則說明dp[m+2v]的價值更大。以此類推， 我們可以得到一個全新的序列：

[dp[m], dp[m+v] - p, dp[m+2v] - 2p, ... dp[i-v] - (i div v - 1)p]

這個時候，我們已經消除了揹包容量變化帶來的偏差，我們可以放心地從其中選擇最值作為最佳的狀態轉移了。但是還有一個小問題，有可能最值是不成立的，舉個例子，如果說我們發現dp[m+2v] - 2p的值是最大的，但是由於item這個物品最多獲取cnt個，如果從m+2v這個狀態轉移到i，需要的數量超過cnt，那麼這也是一個無效的轉移。我們需要拋開它，繼續往下查找次優的結果。

對於區間內最值的維護，單調隊列非常合適，我們可以保證隊首的元素是最優的，如果隊首的元素不合法，那麼我們可以很方便地彈出獲取次優解。也就是說我們通過單調隊列維護了[dp[m], dp[m+v] - p, dp[m+2v] - 2p, ... dp[i-v] - (i div v - 1)p]這個區間的最值，這也是單調隊列最常用的場景。

算法流程

我們整理一下上面的思路，可以整理出整個算法運行的流程。

首先我們需要一重循環來遍歷物品，這個是肯定跑不了的。無論用什麼算法用什麼優化，我們都需要遍歷物品，物品是決策的基礎。在01揹包和二進制表示法當中，第二重循環就是直接遍歷揹包容量了。但是顯然，在當前算法當中，我們不能這麼做。因為前文當中說到，我們需要用單調隊列來維護[dp[m], dp[m+v] - p, dp[m+2v] - 2p, ... dp[i-v] - (i div v - 1)p]這樣一個序列，所以我們需要按照這個序列的順序來遍歷揹包容量。我們關注到起始狀態是dp[m]，這個m代表分組，也就是物品體積的餘數。

舉個例子，如果物品i的體積是5，那麼m有0，1，2，3，4這5種取值，其實這也是5的餘數。相當於我們通過餘數將揹包容量進行分組，這樣我們維護不同分組下的序列。這些分組拼裝在一起就是整個揹包容量。

下面我們來看下代碼，結合上面的敘述會更直觀一些：

由於我們要實現單調隊列，並且從左右兩端都會進行讀取操作，所以我們使用雙端隊列來實現

首先我們來看循環變量，最外層循環的是item，這個已經確定了，i循環的是v的餘數。即商品i的重量的餘數，也就是對於商品i來說整個被揹包容量分組的數量。然後我們針對每一個分組單獨計算最優值。m表示這個數列的數量，就是揹包容量減去餘數之後除以商品的體積。所以我們要維護的序列就是[i, i+v, i+2v,..., i+mv]，j循環的是這個序列。

為了公平起見，我們要用dp[i]作為標準來衡量整個序列當中的價值。對於狀態j * v + i來說，我們把它減去j個item的價值，也就是放到dp[i]一個起跑線來衡量價值。所以val = dp[j * v + i] - j * p。

針對單調隊列deq來說，這是一個遞減的隊列。也就是說隊列頭部的元素是最大值，末尾是最小值。我們

這些邊界條件應該還好，問題不是很大，問題比較大的是if deq[0][1] < j - cnt這個判斷。這個判斷當中隱藏了兩個要點，我們一個一個來說。

首先，deq這個隊列當中每個節點有兩個值，一個是val就是dp數組當中存儲的價值，另一個是j，是序列的位置或者說狀態，注意，它不等於物品拿了的個數。由於題目當中有物品拿取數量的限制，也就是說並不是所有的轉移都是合法的。我們需要保證從隊列的狀態轉移到當前狀態需要的物品個數小於等於最大數量cnt，如果大於就是非法。當前狀態是j，隊列頭部元素狀態是deq[0][1]，也就是說 j - deq[0][1] > cnt的話就非法。

因為deq隊列當中頭部元素值是最大的，所以我們優先考慮從頭部進行轉移到當前狀態。轉移是通過拿取物品進行的，所以我們需要進行物品數量的判斷，如果不滿足需要進行彈出，這個是第一個要點。

第二個點是，為什麼這裡用if判斷而不是while呢？

因為對於j來說，j-1的狀態已經更新過了，也就是說隊列頭部的元素必然對j-1是合法的。也就是說j-1的數量距離j-1最多也就是cnt，那麼對於j而言最多也就增加了1，我們最多隻需要一次彈出就好了。當然也可以用while循環，只不過沒有必要。所以如果看不懂的話，這裡寫成while循環也是一樣的。

最後，我們來分析一下它的複雜度。對於物品i來說，它如果它的體積是v，那麼我們一共可以分成v組。每組當中的數量是volume / v，所以

總結

到這裡，多重揹包的單調優化解法就介紹完了。單調優化是動態規劃算法當中非常常用的一種優化方法，並不只是可以應用在多重揹包問題上，在許多場景下都適用。不過前提是需要我們對於狀態之間的關係，以及轉移前後帶來的影響全部思考清楚。

從代碼上來說，動態規劃實在是非常簡單，一般不會超過幾十行，我們今天的算法主體也才12行，但是這短短的代碼中間藏了大量的信息和思考。對於初學者而言，

今天的文章就是這些，如果覺得有所收穫，請順手點個關注或者轉發吧，你們的舉手之勞對我來說很重要。

閱讀更多 承志的算法課堂 的文章

關鍵字: 數據結構 複雜度 單調