- 相關推薦
用動態規劃法與回溯法實現0-1背包問題的比較
1背包問題0-1背包問題：給定n種物品和一背包。物品i的重量是Wi，其價值為Vi，背包的容量為C。問應如何選擇裝入背包中物品，使得裝入背包中物品的總價值最大？
對于一個實例：物品種類N=4，背包容量C=10，物品重量數組W={3，5，2，1}，相應價值數組V={9，10，7，4}。找一個n元0-1向量（x1，x2，x3….xn）xi∈{0,1},1≤i≤n.使得
，
達到最大。下面分別以動態規劃法和回溯法來解決這個實例。
2動態規劃法
動態規劃法的基本思想是將待求解問題分解成若干個子問題，先求解子問題，然后從這些子問題的解得到原問題的解。用一個表來保存記錄所有已解決的子問題的答案，在需要的時候再找出已求得的答案，避免重復的計算。
動態規劃法適用于解最優化問題。通常可按以下4個步驟：
(1)找出最優解的性質并刻畫其結構特征。
(2)遞歸的定義最優解。
(3)以自底向上的方式計算出最優值。
(4)根據計算最優值時到得的信息，構造最優解。
對于所給0-1背包問題的子問題：
，
的最優值為m（i，j），即m（i，j）是背包容量為j，可懸著物品為i,i+1,….,n時0-1背包問題的最優值。由于0-1背包問題的最優子結構性質，可以建立計算m（i，j）的如下遞歸式：
（1.1）
（1.2）
從上面算法的執行過程中可以看出假設有Q（n）個子問題,每一個子問題最多需要m次決策,則計算的頻率為nm,回溯的頻率為n，那么整個過程的算法的時間復雜度為T（n）=nm+n，即為Q（nm）。
3回溯法。
回溯法在包含問題的所有解的解空間樹中,按照深度優先的策略,從根結點出發搜索解空間樹。回溯算法搜索至解空間樹的任一結點時,總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含,則跳過對以該結點為根的子樹的系統搜索,逐層向其祖先結點回溯。否則,進入該子樹,繼續按深度優先的策略進行搜索。回溯法在用來求問題的所有解時,要回溯到根,且根結點的所有子樹都已被搜索遍才結束。簡單地說就是確定解空間,建立解空間樹,用深度優先搜索算法遞歸搜索解空間樹,并同時注意剪枝。
用回溯法解題的步驟：
(1)針對所給問題定義問題的解空間；
(2)確定易于搜索的解空間結構；
(3)以深度優先方式搜索解空間,并在搜索過程中用剪枝函數避免無效的搜索。
根據上述0-1背包問題的數學描述解向量可以表示成X={X,X,...X|X=0或=1}若X=0,表示第i個物品不裝入背包，X=1，表示將第i個物品裝入背包。
可以用樹的形式將解空間表達出來。樹中從第i層到第i+1層的邊上的值表示解向量中X的取值，并假定第i層的左子樹描述第i個物品被裝入背包的情況，右子樹描述第i個物品被拒絕的情況。則該0-1背包問題的狀態空間樹就表示為一棵高度為n的完全二叉樹。若n=3時則此0-1背包問題的解空間的結構如圖1-1所示。從根結點到葉子結點的任一路徑就對應解空間中的一個解向量
圖1-1n=3時，0-1背包問題的解空間樹
用回溯法求解0-1背包問題時，可以按照物品的單位價值從大到小排序。計算當前節點的上界,搜索左子樹。只有當右子樹包含可行解時才搜索右子樹。剪去右子樹的條件是當前價值加上剩余物品的總價值小于當前的最優總價值時,不需搜索右子樹,可將右子樹剪去。回溯法用一定的剪枝進行優化,算法的時間復雜度為O(n*2n),n為物品個數。
4總結
動態規劃算法：動態規劃可以把困難得多階段決策變換為一系列相互聯系比較容易的單階段問題。對于背包問題可以對子過程用枚舉法求解,而且約束條件越多,決策的搜索范圍越小,求解也越容易。但是對于規模較大的問題它并不是一個理想的算法。最重要的原因就是它的維數障礙。即計算和存儲量的需要對于狀態空間和決策空間的維數的增長呈指數增長關系，這樣驚人的增長速度是計算機難以承受的。這就使得直接的動態規劃方法求解規劃較大的背包問題發生了困難，且目前尚沒有好的解決辦法。
回溯法：回溯法需要為問題定義一個解空間,這個解空間必須至少包含問題的一個解(可能是最優的)。使用遞歸回溯法解決背包問題的優點在于它算法思想簡單,而且它能完全遍歷搜索空間,肯定能找到問題的最優解。但是由于此問題解的總組合數有2個,因此,隨著物件數n的增大,其解的空間將以2級增長,當n大到一定程度上,用此算法解決背包問題將是不現實的。
用此兩種方法都能得到問題的最優解，從其時間復雜度來看，兩者的速度都較慢。
【用動態規劃法與回溯法實現0-1背包問題的比較】相關文章：
比較的特殊表達法初探01-08
比較法楷書教學探索02-25
“聽說法”與“交際法”的比較及啟示08-17
比較法在物理中的應用08-17
歐美產品責任法比較及啟示02-20
儒法之比較及其現代意義02-24
運用改換比較法培養語感08-17
國際法與國內法關系中日之比較02-20
產品責任法相關問題比較11-18