0/1背包問題0/1背包問題

0/1背包問題是給定n個重量為{w1,w2,…

,wn}、價值為{v1,v2,…

,vn}的物品和一個容量為C的背包，求這些物品中的一個最有價值的子集，并且要能夠裝到背包中。

10w1=7v1=42w2=3v2=12w3=4v3=40w4=5v4=25背包物品1物品2物品3物品4蠻力法

就像寶劍不是撬棍一樣，科學也很少使用蠻力。－－－EdwardLytton把事情做“好‘常常是浪費時間。－－－RobertByrne(撞球大師，臺球選手和作家）

蠻力法的設計思想蠻力法的設計思想：是一種簡單直接地解決問題的方法，常常直接基于問題的描述。例：計算ann次an=a×a×…×a蠻力法所賴的基本技術——掃描技術關鍵——依次處理所有元素基本的掃描技術——遍歷（1）集合的遍歷（2）線性表的遍歷（3）樹的遍歷（4）圖的遍歷

雖然巧妙和高效的算法很少來自于蠻力法，基于以下原因，蠻力法也是一種重要的算法設計技術：

（1）理論上，蠻力法可以解決可計算領域的各種問題。（2）蠻力法經常用來解決一些較小規模的問題。（3）對于一些重要的問題蠻力法可以產生一些合理的算法，他們具備一些實用價值，而且不受問題規模的限制。（4）蠻力法可以作為某類問題時間性能的底限，來衡量同樣問題的更高效算法。用蠻力法求解

用蠻力法解決0/1背包問題，需要考慮給定n個物品集合的所有子集，找出所有可能的子集（總重量不超過背包容量的子集），計算每個子集的總價值，然后在他們中找到價值最大的子集。10w1=7v1=42w2=3v2=12w3=4v3=40w4=5v4=25背包物品1物品2物品3物品48{1,4}1216{1,2,3,4}19序號子集總重量總價值序號子集總重量總價值1φ009{2,3}7522{1}74210{2,4}8373{2}31211{3,4}9654{3}44012{1,2,3}14不可行5{4}52513{1,2,4}156{1,2}105414{1,3,4}167{1,3}11不可行15{2,3,4}12不可行不可行不可行不可行不可行對于一個具有n個元素的集合，其子集數量是2n，所以，不論生成子集的算法效率有多高，蠻力法都會導致一個Ω(2n)的算法。貪心法

貪婪，我找不到一個更好的詞來描述它，它就是好！它就是對！它就是有效！

－－－美國演員道格拉思，在影片《華爾街》中的臺詞

概述

貪心法的設計思想

貪心法的求解過程

貪心法在解決問題的策略上目光短淺，只根據當前已有的信息就做出選擇，而且一旦做出了選擇，不管將來有什么結果，這個選擇都不會改變。換言之，貪心法并不是從整體最優考慮，它所做出的選擇只是在某種意義上的局部最優。這種局部最優選擇并不總能獲得整體最優解（OptimalSolution），但通常能獲得近似最優解（Near-OptimalSolution）。貪心法的設計思想例：用貪心法求解付款問題。假設有面值為5元、2元、1元、5角、2角、1角的貨幣，需要找給顧客4元6角現金，為使付出的貨幣的數量最少，首先選出1張面值不超過4元6角的最大面值的貨幣，即2元，再選出1張面值不超過2元6角的最大面值的貨幣，即2元，再選出1張面值不超過6角的最大面值的貨幣，即5角，再選出1張面值不超過1角的最大面值的貨幣，即1角，總共付出4張貨幣。在付款問題每一步的貪心選擇中，在不超過應付款金額的條件下，只選擇面值最大的貨幣，而不去考慮在后面看來這種選擇是否合理，而且它還不會改變決定：一旦選出了一張貨幣，就永遠選定。付款問題的貪心選擇策略是盡可能使付出的貨幣最快地滿足支付要求，其目的是使付出的貨幣張數最慢地增加，這正體現了貪心法的設計思想。貪心法求解的問題的特征：（1）最優子結構性質當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構性質，也稱此問題滿足最優性原理。（2）貪心選擇性質所謂貪心選擇性質是指問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來得到。

動態規劃法通常以自底向上的方式求解各個子問題，而貪心法則通常以自頂向下的方式做出一系列的貪心選擇。

貪心法的求解過程

用貪心法求解問題應該考慮如下幾個方面：（1）候選集合C：為了構造問題的解決方案，有一個候選集合C作為問題的可能解，即問題的最終解均取自于候選集合C。例如，在付款問題中，各種面值的貨幣構成候選集合。（2）解集合S：隨著貪心選擇的進行，解集合S不斷擴展，直到構成一個滿足問題的完整解。例如，在付款問題中，已付出的貨幣構成解集合。

（3）解決函數solution：檢查解集合S是否構成問題的完整解。例如，在付款問題中，解決函數是已付出的貨幣金額恰好等于應付款。

（4）選擇函數select：即貪心策略，這是貪心法的關鍵，它指出哪個候選對象最有希望構成問題的解，選擇函數通常和目標函數有關。例如，在付款問題中，貪心策略就是在候選集合中選擇面值最大的貨幣。（5）可行函數feasible：檢查解集合中加入一個候選對象是否可行，即解集合擴展后是否滿足約束條件。例如，在付款問題中，可行函數是每一步選擇的貨幣和已付出的貨幣相加不超過應付款。

貪心法的一般過程Greedy(C)//C是問題的輸入集合即候選集合{S={};//初始解集合為空集

while(notsolution(S))//集合S沒有構成問題的一個解

{x=select(C);//在候選集合C中做貪心選擇

iffeasible(S,x)//判斷集合S中加入x后的解是否可行

S=S+{x};C=C-{x};}returnS;}用貪心法解至少有三種看似合理的貪心策略：（1）選擇價值最大的物品，因為這可以盡可能快地增加背包的總價值。但是，雖然每一步選擇獲得了背包價值的極大增長，但背包容量卻可能消耗得太快，使得裝入背包的物品個數減少，從而不能保證目標函數達到最大。（2）選擇重量最輕的物品，因為這可以裝入盡可能多的物品，從而增加背包的總價值。但是，雖然每一步選擇使背包的容量消耗得慢了，但背包的價值卻沒能保證迅速增長，從而不能保證目標函數達到最大。（3）選擇單位重量價值最大的物品，在背包價值增長和背包容量消耗兩者之間尋找平衡。

應用第三種貪心策略，每次從物品集合中選擇單位重量價值最大的物品，如果其重量小于背包容量，就可以把它裝入，并將背包容量減去該物品的重量，然后我們就面臨了一個最優子問題——它同樣是背包問題，只不過背包容量減少了，物品集合減少了。因此背包問題具有最優子結構性質。

12050背包180190200(a)三個物品及背包(b)貪心策略1(c)貪心策略2(d)貪心策略3

50301020203020/30201010/203010例如，有3個物品，其重量分別是{20,30,10}，價值分別為{60,120,50}，背包的容量為50，應用三種貪心策略裝入背包的物品和獲得的價值如圖所示。分治法

無論人們在祈禱什么，他們總是在祈禱一個奇跡．每一個祈禱都可以簡化為：偉大的上帝啊，請讓兩個二相加不等于四吧．－－屠格涅夫

概

述

分治法的設計思想

分治法的求解過程

將一個難以直接解決的大問題，劃分成一些規模較小的子問題，以便各個擊破，分而治之。更一般地說，將要求解的原問題劃分成k個較小規模的子問題，對這k個子問題分別求解。如果子問題的規模仍然不夠小，則再將每個子問題劃分為k個規模更小的子問題，如此分解下去，直到問題規模足夠小，很容易求出其解為止，再將子問題的解合并為一個更大規模的問題的解，自底向上逐步求出原問題的解。

分治法的設計思想

2.獨立子問題：各子問題之間相互獨立，這涉及到分治法的效率，如果各子問題不是獨立的，則分治法需要重復地解公共的子問題。1.平衡子問題：最好使子問題的規模大致相同。也就是將一個問題劃分成大小相等的k個子問題（通常k＝2），這種使子問題規模大致相等的做法是出自一種平衡（Balancing）子問題的思想，它幾乎總是比子問題規模不等的做法要好。啟發式規則：子問題1的規模是n/2子問題1的解子問題2的解子問題2的規模是n/2原問題的解原問題的規模是n分治法的典型情況分治法的求解過程

一般來說，分治法的求解過程由以下三個階段組成：（1）劃分：既然是分治，當然需要把規模為n的原問題劃分為k個規模較小的子問題，并盡量使這k個子問題的規模大致相同。（2）求解子問題：各子問題的解法與原問題的解法通常是相同的，可以用遞歸的方法求解各個子問題，有時遞歸處理也可以用循環來實現。（3）合并：把各個子問題的解合并起來，合并的代價因情況不同有很大差異，分治算法的有效性很大程度上依賴于合并的實現。例：計算an，應用分治技術得到如下計算方法：3432328131319313193333分解問題求解每個子問題合并子問題的解??éù?íì>′==1122naanaannn如果如果減治法普盧塔克說，薩特斯為了告訴他的士兵堅韌和智慧比蠻力更重要的道理，把兩匹馬帶到他們面前，然后讓兩個人扒光馬的尾毛．一個人是魁梧的大力士，他抓住尾巴扒了又扒，但一點效果也沒有；另一個人是一個精明的、長相狡黠的裁縫，他微笑著，每次扒掉一根毛，很快就把尾巴拔得光禿禿的。減治法的設計思想

規模為n的原問題的解與較小規模（通常是n/2）的子問題的解之間具有關系：（1）原問題的解只存在于其中一個較小規模的子問題中；（2）原問題的解與其中一個較小規模的解之間存在某種對應關系。由于原問題的解與較小規模的子問題的解之間存在這種關系，所以，只需求解其中一個較小規模的子問題就可以得到原問題的解。子問題的規模是n/2子問題的解原問題的解原問題的規模是n減治法的設計思想例：計算an的值，應用減治技術得到如下計算方法：應用分治法得到an的計算方法是：

O(log2n)O(nlog2n)???íì>′>==-且是奇數且是偶數1)(1)(122)1(22naananaannn所以，通常來說，應用減治法處理問題的效率是很高的，一般是O(log2n)數量級。

減治法只對一個子問題求解，并且不需要進行解的合并。應用減治法（例如減半法）得到的算法通常具有如下遞推式：

動態規劃法

思想，就像幽靈一樣……在它自己解釋自己之前，必須先告訴它些什么。－－狄更斯

概

述

1最優化問題2最優性原理3動態規劃法的設計思想

最優化問題：有n個輸入，它的解由這n個輸入的一個子集組成，這個子集必須滿足某些事先給定的條件，這些條件稱為約束條件，滿足約束條件的解稱為問題的可行解。滿足約束條件的可行解可能不只一個，為了衡量這些可行解的優劣，事先給出一定的標準，這些標準通常以函數的形式給出，這些標準函數稱為目標函數，使目標函數取得極值（極大或極小）的可行解稱為最優解，這類問題就稱為最優化問題。

1最優化問題例：付款問題：超市的自動柜員機（POS機）要找給顧客數量最少的現金。假定POS機中有n張面值為pi(1≤i≤n)的貨幣，用集合P={p1,p2,…,pn}表示，如果POS機需支付的現金為A，那么，它必須從P中選取一個最小子集S，使得

（式6.1）如果用向量X=(x1,x2,…,xn)表示S中所選取的貨幣，則

（式6.2）

那么，POS機支付的現金必須滿足（式6.3）并且（式6.4）

在付款問題中，集合P是該問題的輸入，滿足式6.1的解稱為可行解，式6.2是解的表現形式，因為向量X中有n個元素，每個元素的取值為0或1，所以，可以有2n個不同的向量，所有這些向量的全體構成該問題的解空間，式6.3是該問題的約束條件，式6.4是該問題的目標函數，使式6.4取得極小值的解稱為該問題的最優解。

動態規劃法的設計思想

動態規劃法將待求解問題分解成若干個相互重疊的子問題，每個子問題對應決策過程的一個階段，一般來說，子問題的重疊關系表現在對給定問題求解的遞推關系（也就是動態規劃函數）中，將子問題的解求解一次并填入表中，當需要再次求解此子問題時，可以通過查表獲得該子問題的解而不用再次求解，從而避免了大量重復計算。原問題的解原問題……填表子問題1子問題2子問題n動態規劃法的求解過程n=5時分治法計算斐波那契數的過程。

F(5)F(4)F(3)F(3)F(2)F(2)F(1)F(2)F(1)F(1)F(0)F(1)F(0)F(1)F(0)例：計算斐波那契數：01234567890112358132134動態規劃法求解斐波那契數F(9)的填表過程：注意到，計算F(n)是以計算它的兩個重疊子問題

F(n-1)和F(n-2)的形式來表達的，所以，可以設計一張表填入n+1個F(n)的值。

用動態規劃法求解的問題具有特征：能夠分解為相互重疊的若干子問題；滿足最優性原理（也稱最優子結構性質）：該問題的最優解中也包含著其子問題的最優解。（用反證法）分析問題是否滿足最優性原理：先假設由問題的最優解導出的子問題的解不是最優的;然后再證明在這個假設下可構造出比原問題最優解更好的解，從而導致矛盾。

動態規劃法設計算法一般分成三個階段：（1）分段：將原問題分解為若干個相互重疊的子問題；（2）分析：分析問題是否滿足最優性原理，找出動態規劃函數的遞推式；（3）求解：利用遞推式自底向上計算，實現動態規劃過程。動態規劃法利用問題的最優性原理，以自底向上的方式從子問題的最優解逐步構造出整個問題的最優解。用動態規劃法求解

在0/1背包問題中，物品i或者被裝入背包，或者不被裝入背包，設xi表示物品i裝入背包的情況，則當xi=0時，表示物品i沒有被裝入背包，xi=1時，表示物品i被裝入背包。根據問題的要求，有如下約束條件和目標函數：

（式6.9）（式6.10）于是，問題歸結為尋找一個滿足約束條件式6.9，并使目標函數式6.10達到最大的解向量X=(x1,x2,…,xn)。證明0/1背包問題滿足最優性原理。設(x1,x2,…,xn)是所給0/1背包問題的一個最優解，則(x2,…,xn)是下面一個子問題的最優解：如若不然，設(y2,…,yn)是上述子問題的一個最優解，則因此，

這說明(x1,y2,…,yn)是所給0/1背包問題比(x1,x2,…,xn)更優的解，從而導致矛盾。

0/1背包問題可以看作是決策一個序列(x1,x2,…,xn)，對任一變量xi的決策是決定xi=1還是xi=0。在對xi-1決策后，已確定了(x1,…,xi-1)，在決策xi時，問題處于下列兩種狀態之一：（1）背包容量不足以裝入物品i，則xi=0，背包不增加價值；（2）背包容量可以裝入物品i，則xi=1，背包的價值增加了vi。這兩種情況下背包價值的最大者應該是對xi決策后的背包價值。令V(i,j)表示在前i(1≤i≤n)個物品中能夠裝入容量為j（1≤j≤C）的背包中的物品的最大值，則可以得到如下動態規劃函數：

V(i,0)=V(0,j)=0（式6.11）（式6.12）式6.11表明：把前面i個物品裝入容量為0的背包和把0個物品裝入容量為j的背包，得到的價值均為0。式6.12的第一個式子表明：如果第i個物品的重量大于背包的容量，則裝入前i個物品得到的最大價值和裝入前i-1個物品得到的最大價值是相同的，即物品i不能裝入背包；第二個式子表明：如果第i個物品的重量小于背包的容量，則會有以下兩種情況：（1）如果把第i個物品裝入背包，則背包中物品的價值等于把前i-1個物品裝入容量為j-wi的背包中的價值加上第i個物品的價值vi；（2）如果第i個物品沒有裝入背包，則背包中物品的價值就等于把前i-1個物品裝入容量為j的背包中所取得的價值。顯然，取二者中價值較大者作為把前i個物品裝入容量為j的背包中的最優解。

根據動態規劃函數，用一個(n+1)×(C+1)的二維表V，V[i][j]表示把前i個物品裝入容量為j的背包中獲得的最大價值。

0例如，有5個物品，其重量分別是{2,2,6,5,4}，價值分別為{6,3,5,4,6}，背包的容量為10。x5=1x4=0x3=0x2=1x1=1

012345678910

00000000000w1=2v1=6100666666666w2=2v2=3200669999999w3=6v3=5300669999111114w4=5v4=44006699910111314w5=5v5=6500669912121515150按下述方法來劃分階段：第一階段，只裝入前1個物品，確定在各種情況下的背包能夠得到的最大價值；第二階段，只裝入前2個物品，確定在各種情況下的背包能夠得到的最大價值；依此類推，直到第n個階段。最后，V(n,C)便是在容量為C的背包中裝入n個物品時取得的最大價值。為了確定裝入背包的具體物品，從V(n,C)的值向前推，如果V(n,C)>V(n-1,C)，表明第n個物品被裝入背包，前n-1個物品被裝入容量為C-wn的背包中；否則，第n個物品沒有被裝入背包，前n-1個物品被裝入容量為C的背包中。依此類推，直到確定第1個物品是否被裝入背包中為止。由此，得到如下函數：

（式6.13）

回溯法

復雜問題常常有很多的可能解，這些可能解構成了問題的解空間。解空間也就是進行窮舉的搜索空間，所以，解空間中應該包括所有的可能解。確定正確的解空間很重要，如果沒有確定正確的解空間就開始搜索，可能會增加很多重復解，或者根本就搜索不到正確的解。問題的解空間(a)二維搜索空間無解(b)三維搜索空間的解圖8.1錯誤的解空間將不能搜索到正確答案例如：桌子上有6根火柴棒，要求以這6根火柴棒為邊搭建4個等邊三角形。

對于任何一個問題，可能解的表示方式和它相應的解釋隱含了解空間及其大小。例如，對于有n個物品的0/1背包問題，其可能解的表示方式可以有以下兩種：（1）可能解由一個不等長向量組成，當物品i(1≤i≤n)裝入背包時，解向量中包含分量i，否則，解向量中不包含分量i，當n=3時，其解空間是：

{(),(1),(2),(3),(1,2),(1,3),(2,3),(1,2,3)}（2）可能解由一個等長向量{x1,x2,…,xn}組成，其中xi=1(1≤i≤n)表示物品i裝入背包，xi=0表示物品i沒有裝入背包，當n=3時，其解空間是：{(0,0,0),(0,0,1),(0,1,0),(1,0,0),(0,1,1),(1,0,1),(1,1,0),(1,1,1)}為了用回溯法求解一個具有n個輸入的問題，一般情況下，將其可能解表示為滿足某個約束條件的等長向量X=(x1,x2,…,xn)，其中分量xi(1≤i≤n)的取值范圍是某個有限集合Si={ai1,ai2,…,airi}，所有可能的解向量構成了問題的解空間。

問題的解空間一般用解空間樹（SolutionSpaceTrees,也稱狀態空間樹）的方式組織，樹的根結點位于第1層，表示搜索的初始狀態，第2層的結點表示對解向量的第一個分量做出選擇后到達的狀態，第1層到第2層的邊上標出對第一個分量選擇的結果，依此類推，從樹的根結點到葉子結點的路徑就構成了解空間的一個可能解。對于n=3的0/1背包問題，其解空間樹如圖8.2所示，樹中的8個葉子結點分別代表該問題的8個可能解。

對物品1的選擇對物品3的選擇對物品2的選擇1111110000000112345781112141531069解空間樹的動態搜索（1）

回溯法從根結點出發，按照深度優先策略遍歷解空間樹，搜索滿足約束條件的解。在搜索至樹中任一結點時，先判斷該結點對應的部分解是否滿足約束條件，或者是否超出目標函數的界，也就是判斷該結點是否包含問題的（最優）解，如果肯定不包含，則跳過對以該結點為根的子樹的搜索，即所謂剪枝（Pruning）；否則，進入以該結點為根的子樹，繼續按照深度優先策略搜索。用回溯法解例如，對于n=3的0/1背包問題，三個物品的重量為{20,15,10}，價值為{20,30,25}，背包容量為25，從圖8.2所示的解空間樹的根結點開始搜索，搜索過程如下：1不可行解價值=20價值=55價值=30價值=25價值=01111000000112811121415131069不可行解分支限界法分支限界法首先確定一個合理的限界函數，并根據限界函數確定目標函數的界[down,up]。然后，按照廣度優先策略遍歷問題的解空間樹，在分支結點上，依次搜索該結點的所有孩子結點，分別估算這些孩子結點的目標函數的可能取值，如果某孩子結點的目標函數可能取得的值超出目標函數的界，則將其丟棄，因為從這個結點生成的解不會比目前已經得到的解更好；否則，將其加入待處理結點表（以下簡稱表PT）中。依次從表PT中選取使目標函數的值取得極值的結點成為當前擴展結點，重復上述過程，直到找到最優解。解空間樹的動態搜索（2）隨著這個遍歷過程的不斷深入，表PT中所估算的目標函數的界越來越接近問題的最優解。當搜索到一個葉子結點時，如果該結點的目標函數值是表PT中的極值（對于最小化問題，是極小值；對于最大化問題，是極大值），則該葉子結點對應的解就是問題的最優解；否則，根據這個葉子結點調整目標函數的界（對于最小化問題，調整上界；對于最大化問題，調整下界），依次考察表PT中的結點，將超出目標函數界的結點丟棄，然后從表PT中選取使目標函數取得極值的結點繼續進行擴展。用分支限界法解

例：0/1背包問題。假設有4個物品，其重量分別為(4,7,5,3)，價值分別為(40,42,25,12)，背包容量W=10。首先，將給定物品按單位重量價值從大到小排序，結果如下：物品重量(w)價值(v)價值/重量(v/w)144010274263525543124

應用貪心法求得近似解為(1,0,0,0)，獲得的