背包算法概要.ppt

《背包算法概要.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、KnapsackProblem(背包問題)指導教授：巫沛倉博士學生：宋明賢TheKnapsackProblem(背包問題)Def:所謂KnapsackProblem，是指有N個物品和一個背包，其中:物品具有重量(w1,w2,…,wn)和利潤(p1,p2,…,pn)背包的最大重量承受限制為W問如何取物可得最高價值?此問題可以表示如下:2KnapsackProblem可分成兩種問題型態:FractionalKnapsackProblem:物品可被切割，亦即取物時可取部份採用貪婪法則(GreedyApproach)0/1KnapsackProblem:物品不可被

2、切割，亦即取物時得取全部採用動態規劃(DynamicProgramming)KnapsackProblem問題型態3GreedyApproachv.s.DynamicProgramming對於具有限制的最佳化問題，可以採用“貪婪法則”或“動態規劃”來設計演算法則。所謂具有限制條件的最佳化問題，是指可以將這一個問題表示成為具有一個目標函數(ObjectiveFunction)與一些限制函數(ConstraintFunction；或稱限制條件)的式子。對於求解具有限制條件的最佳化問題時所得到的不同答案類型而言:符合限制函數(條件)的所有答案，一般通稱為可行解(F

3、easibleSolution)但是在這一群可行解中，如果能夠讓目標函數最佳化，則這一個可行解就稱為最佳解(OptimalSolution)4GreedyApproachv.s.DynamicProgrammingGreedyApproach是一種階段性(Stage)的方法具有一選擇程序(SelectionProcedure)，自某起始點(值)開始，在每一個階段逐一檢查每一個輸入是否適合加入答案中，重複經過多個階段後，即可順利獲得最佳解一個選擇程序正確與否，會影響貪婪法則所設計出之演算法在執行過後的答案是否為最佳答案。較為簡單如果所要處理的最佳化問題無法找到

4、一個選擇程序，則需要考慮所有的可能情況，就是屬於DynamicProgramming5GreedyApproachv.s.DynamicProgrammingDynamicProgramming先把所有的情況都看過一遍，才去挑出最佳的結果考慮問題所有可能的情況，將最佳化問題的目標函數表示成一個遞迴關係式，結合Table的使用以找出最佳解6-以下列範例說明上述兩種類型的背包問題:背包可承擔的最大重量:30lb(磅)三個物品之重量及其利潤:Item1:5lb,$50Item2:10lb,$60Item3:20lb,$140範例5lb$50item110lb$60

5、item2$14020lbitem330lbMax.Knapsack7FractionalKnapsackProblem物品可被切割，亦即取物時可取部份採用GreedyApproach，因此需設定「選擇程序」。由於物品放入背包可以獲得利潤，但是也同時會增加重量，所以共有三種可供使用的選擇程序，分別是:利潤:採用最大利潤優先的選擇程序。自利潤最大之物品依序取物，直到物品拿完或負重=W為止，就可以得到一個可行解重量:採用最小重量優先的選擇程序。自重量最小之物品依序取物，直到物品拿完或負重=W為止，就可以得到一個可行解利潤與重量比:採用最大利潤與重量比的選擇程序。

6、自利潤與重量比最大之物品依序取物，直到物品拿完或負重=W為止，就可以得到一個可行解以上三種選擇程序，只有利潤與重量比可以得到一個最佳解，其餘兩個只能得到可行解因此，貪婪法則的選擇程序適題與否，對於是否可以得到一個問題之最佳解具有決定性的影響8根據題目定義，我們可以得到下列表格:選擇程序採“最大利潤優先”:Step1:取20bl的Item1，可得利潤為$140，背包剩餘重量:10blStep2:取10bl的Item2，連同Step1所取之20bl的Item1，可得總利潤為$200，背包剩餘重量:0blStep3:因為背包已無剩餘重量，故完全無法取得Item3所

7、得總利潤=$200Item重量(bl)利潤利潤/重量比15$5010210$606320$1407最大利潤優先5lb$50item110lb$60item2$14020lbitem330lbMax.KnapsackGreedySolution$60$140=$20020lb10lb9根據題目定義，我們可以得到下列表格:選擇程序採“最小重量優先”:Step1:取5bl的Item1，可得利潤為$50，背包剩餘重量:25blStep2:取10bl的Item2，連同Step1所取之5bl的Item1，可得總利潤為$110，背包剩餘重量:15blStep3:由於背包

8、剩餘重量為15bl，而Item3的重量有20bl，因