回溯法-背包問題

問題描述:

給定n種物品和一背包。物品i的重量是wi,其價值為pi,背包的容量為C。問應如何選擇裝入背包的物品,使得裝入背包中物品的總價值最大?

n個物品中選擇部分物品,可知,問題的解空間是子集樹。比如物品數目n=3時,其解空間樹如下圖

思路:

邊為1代表選擇該物品,邊為0代表不選擇該物品?；厮菟阉鬟^程,如果來到了葉子節點,表示一條搜索路徑結束,如果該路徑上存在更優的解,則保存下來。如果不是葉子節點,是中點的節點(如B),就遍歷其子節點(D和E),如果子節點滿足剪枝條件,就繼續回溯搜索子節點。

邊界條件是當前遞歸深度到葉子節點;

此時判斷是不是更優的解;

約束條件是放入當前物品到背包后,背包內物品總重量不超過背包容量,則繼續搜索,直至葉子節點。

回溯點,中間節點

提交代碼

// 還未親測,后續補充

回溯法概述:

回溯法(探索與回溯法)是一種優先搜索法,又稱為試探法,按優先條件向前探索,以達到目標。但當探索到某一步重新選擇,這種走不通就退回再走的技術為回溯法,而滿足回溯條件的某個狀態的點稱為“回溯點”。

在回溯法中,每次擴大當前部分解時,都面臨一個可選的狀態集合,新的部分解就通過在該集合中選擇構造而成,這樣的狀態集合,其結構就是一顆多叉樹。

回溯法解題

應用回溯法求解問題時,首先應明確定義問題的解空間,該解空間應至少包含問題的一個最優解。

在定義了問題的解空間,還需要將解空間有效地組織起來,使得回溯法方便的搜索整個解空間,通常將解空間組織成樹或圖的形式。

確定了問題的解空間結構后,回溯法將從開始結點(根節點)出發,以深度優先的方式搜索整個解空間。

開始結點成為活結點,同時也成為擴展結點,向縱深方向搜索并移至一個新結點,這個新結點就成為一個新的活結點,并成為當前的擴展結點。

如果在當前的擴展結點不能再向縱深方向移動,則當前的擴展結點就成為死結點。此時應往回移動(回溯)至最近的一個活結點,并使其稱為當前的擴展結點。

回溯法以上述工作方式遞歸地在解空間中搜索,直至找到所要求的解或者解空間中已無活結點為止。

運用回溯法解題的三個關鍵

(1)針對給定的問題,定義問題的解空間

(2) 確定易于搜索的解空間結構

(3)以深度優先方式搜索解空間,并且在搜索過程中用剪枝函數避免無效檢索。

一般情況下可以用遞歸函數實現回溯法,遞歸函數模板如下:

void BackTrace(int t){   if(t>n){      Output(x)   }   else{      for(int i=f(n,t);i<=g(n,t);i++){          x[t] = h(i);           if(Constraint(t)&&Bound(t)){                 BackTrace(t+1);           }      }  }}

t 表示遞歸深度,即當前擴展結點在解空間樹中的深度;

n 用來控制遞歸深度,即解空間樹的高度。

當 t>n時,算法已搜索到一個葉子結點,此時由函數Output(x)對得到的可行解x進行記錄或輸出處理。

用 f(n, t)和 g(n, t)分別表示在當前擴展結點處未搜索過的子樹的起始編號和終止編號;

h(i)表示在當前擴展結點處x[t] 的第i個可選值;

函數 Constraint(t)和 Bound(t)分別表示當前擴展結點處的約束函數和限界函數。

若函數 Constraint(t)的返回值為真,則表示當前擴展結點處x[1:t] 的取值滿足問題的約束條件;否則不滿足問題的約束條件。若函數Bound(t)的返回值為真,則表示在當前擴展結點處x[1:t] 的取值尚未使目標函數越界,還需由BackTrace(t+1)對其相應的子樹做進一步地搜索;否則,在當前擴展結點處x[1:t]的取值已使目標函數越界,可剪去相應的子樹。