介紹解決傳統動態規劃算法整數限制和時間復雜度高問題的跳躍點算法設計、實例圖解及實戰。
01
算法的改進
1
●
算法的改進思路
由C［i］［j］的遞歸式(4-11)容易證明：在一般情況下，對每一個確定的i(1≤i≤n)，函數C［i］［j］是關于變量j的階梯狀單調不減函數(事實上，計算C［i］［j］的遞歸式在變量j是連續變量，即為實數時仍成立)。跳躍點是這一類函數的描述特征。在一般情況下，函數C［i］［j］由其全部跳躍點唯一確定，如圖4-9所示。
圖4-9 階梯狀單調不減函數C(i,j)及其跳躍點
利用該類函數由其跳躍點唯一確定的性質，來對0-1背包問題的算法進行改進，具體思路如下：
(1) 對每一個確定的i(1≤i≤n)，用一個表p［i］來存儲函數C［i］［j］的全部跳躍點。對每一個確定的實數j，可以通過查找p［i］來確定函數C［i］［j］的值。p［i］中的全部跳躍點(j，C［i］［j］)按j升序排列。由于函數C［i］［j］是關于j的階梯狀單調不減函數，故p［i］中全部跳躍點的C［i］［j］值也是遞增排列的。
(2) p［i］可通過計算p［i-1］得到。初始時令p［0］={(0貪心算法 背包問題 c，0)}。由于函數C［i］［j］是由函數C［i-1］［j］與函數C［i-1］［j-wi］+vi做max運算得到的。因此，函數C［i］［j］的全部跳躍點包含于函數C［i-1］［j］的跳躍點集p［i-1］與函數C［i-1］［j-wi］+vi的跳躍點集q［i-1］的并集。容易得知，(s，t)∈q［i-1］當且僅當wi≤s≤W且(s-wi，t-vi)∈p［i-1］。因此，容易由p［i-1］來確定跳躍點集q［i-1］，公式為
(3) 另外，設(a，b)和(c，d)是p［i-1］∪q［i-1］中的兩個跳躍點，當c≥a且d
(4) 由此可得，在遞歸地由p［i-1］計算p［i］時，可先由p［i-1］計算出q［i-1］，然后合并p［i-1］和q［i-1］，并清除其中的受控跳躍點得到p［i］。
(5) 構造最優解。
第一步，初始時，i=n，j初始化為p［n］中的最大重量，m初始化為p［n］中的最優值。
第二步，檢查p［i-1］中的所有點(w，v)，如果w+wi=j并且v+vi=m，則xi=1，j=w，m=v，否則xi=0。重復第二步，直到i=0為止。
【例4-5】用跳躍點算法求解4.6.3節的實例。
按照算法的改進思路，具體的求解過程如下：
初始時，令p［0］={(0，0)}。
在該并集中可以看到，跳躍點(2，3)受控于跳躍點(2，6)，因此將(2，3)從并集中清除，得到
在該并集中可以看到，跳躍點(6，5)受控于跳躍點(4，9)，因此將(6，5)從并集中清除，得到
由于跳躍點(13，15)和(15，18)已超出背包的容量W=10，因此將它們清除，得到
在該并集中可以看到，跳躍點(5，4)受控于跳躍點(4貪心算法 背包問題 c，9)，因此將(5，4)從并集中清除，得到
同理，由于跳躍點(11，16)，(12，17)，(13，19)和(14，20)已超出背包的容量W=10，因此將它們清除，得到
在該并集中的受控跳躍點有(4，6)、(7，10)、(8，11)、(9，13)和(10，14)，因此將它們從并集中清除，得到p［5］={(0，0)，(2，6)，(4，9)，(6，12)，(8，15)}。
p［5］中最后的跳躍點(8，15)給出了裝入背包的最優值15及裝入背包的物品重量8。
構造最優解過程：由于p［4］中的(4，9)⊕(4，6)=(8，15)，故x5=1，j=4，m=9；由于p［3］中的所有點⊕(w4，v4)≠(j，m)，故x4=0；p［2］中的所有點⊕(w3，v3)≠(j，m)，故x3=0；p［1］中的(2，6)⊕(2，3)=(4，9)，故x2=1，j=2，m=6；p［0］中的(0，0)⊕(2，6)=(2，6)，故x1=1，j=0，m=0；求得的最優解為(1，1，0，0，1)。
02
實戰
1
●
0-1背包問題的跳躍點算法
首先定義一個()函數，完成跳躍點集合的歸并排序。接收兩個有序的點集，將其歸并為一個有序的點集。其代碼如下：
其次，定義()函數，完成各子問題跳躍點的計算，從而求出原問題的跳躍點，得到問題的最優值。
定義()函數，根據各子問題的跳躍點，逆向遞推構造問題的最優解。其代碼如下：
程序入口——main()函數，在main()函數中，給定5個物品的重量、價值和背包的容量，調用 ()函數得到最優值，再調用 ()函數構造問題的最優解，最后將結果打印輸出到顯示器上。其代碼如下：
輸入結果為
最優解為：［1, 1, 0, 0, 1］
實例講解
算法設計與分析（版）
精彩回顧
秒懂算法
下期預告
秒懂算法
子集樹模型——0-1背包問題的回溯算法
滿m叉樹模型——圖的m可著色問題的回溯算法
排列樹模型——旅行商問題的分支限界法
最大網絡流的增廣路算法
蒙特卡羅算法
02
參考書籍
《算法設計與分析》
ISBN：