背包問題(修改)

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

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

,wn}、價(jià)值為{v1,v2,…

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

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

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

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

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

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

用蠻力法解決0/1背包問題，需要考慮給定n個(gè)物品集合的所有子集，找出所有可能的子集（總重量不超過背包容量的子集），計(jì)算每個(gè)子集的總價(jià)值，然后在他們中找到價(jià)值最大的子集。10w1=7v1=42w2=3v2=12w3=4v3=40w4=5v4=25背包物品1物品2物品3物品48{1,4}1216{1,2,3,4}19序號(hào)子集總重量總價(jià)值序號(hào)子集總重量總價(jià)值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不可行不可行不可行不可行不可行對(duì)于一個(gè)具有n個(gè)元素的集合，其子集數(shù)量是2n，所以，不論生成子集的算法效率有多高，蠻力法都會(huì)導(dǎo)致一個(gè)Ω(2n)的算法。貪心法

貪婪，我找不到一個(gè)更好的詞來描述它，它就是好！它就是對(duì)！它就是有效！

－－－美國(guó)演員道格拉思，在影片《華爾街》中的臺(tái)詞

概述

貪心法的設(shè)計(jì)思想

貪心法的求解過程

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

動(dòng)態(tài)規(guī)劃法通常以自底向上的方式求解各個(gè)子問題，而貪心法則通常以自頂向下的方式做出一系列的貪心選擇。

貪心法的求解過程

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

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

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

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

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

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

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

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

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

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

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

無論人們?cè)谄矶\什么，他們總是在祈禱一個(gè)奇跡．每一個(gè)祈禱都可以簡(jiǎn)化為：偉大的上帝啊，請(qǐng)讓兩個(gè)二相加不等于四吧．－－屠格涅夫

概

述

分治法的設(shè)計(jì)思想

分治法的求解過程

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

分治法的設(shè)計(jì)思想

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

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

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

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

減治法只對(duì)一個(gè)子問題求解，并且不需要進(jìn)行解的合并。應(yīng)用減治法（例如減半法）得到的算法通常具有如下遞推式：

動(dòng)態(tài)規(guī)劃法

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

概

述

1最優(yōu)化問題2最優(yōu)性原理3動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)思想

最優(yōu)化問題：有n個(gè)輸入，它的解由這n個(gè)輸入的一個(gè)子集組成，這個(gè)子集必須滿足某些事先給定的條件，這些條件稱為約束條件，滿足約束條件的解稱為問題的可行解。滿足約束條件的可行解可能不只一個(gè)，為了衡量這些可行解的優(yōu)劣，事先給出一定的標(biāo)準(zhǔn)，這些標(biāo)準(zhǔn)通常以函數(shù)的形式給出，這些標(biāo)準(zhǔn)函數(shù)稱為目標(biāo)函數(shù)，使目標(biāo)函數(shù)取得極值（極大或極?。┑目尚薪夥Q為最優(yōu)解，這類問題就稱為最優(yōu)化問題。

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

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

（式6.2）

那么，POS機(jī)支付的現(xiàn)金必須滿足（式6.3）并且（式6.4）

在付款問題中，集合P是該問題的輸入，滿足式6.1的解稱為可行解，式6.2是解的表現(xiàn)形式，因?yàn)橄蛄縓中有n個(gè)元素，每個(gè)元素的取值為0或1，所以，可以有2n個(gè)不同的向量，所有這些向量的全體構(gòu)成該問題的解空間，式6.3是該問題的約束條件，式6.4是該問題的目標(biāo)函數(shù)，使式6.4取得極小值的解稱為該問題的最優(yōu)解。

動(dòng)態(tài)規(guī)劃法的設(shè)計(jì)思想

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

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)例：計(jì)算斐波那契數(shù)：01234567890112358132134動(dòng)態(tài)規(guī)劃法求解斐波那契數(shù)F(9)的填表過程：注意到，計(jì)算F(n)是以計(jì)算它的兩個(gè)重疊子問題

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

用動(dòng)態(tài)規(guī)劃法求解的問題具有特征：能夠分解為相互重疊的若干子問題；滿足最優(yōu)性原理（也稱最優(yōu)子結(jié)構(gòu)性質(zhì)）：該問題的最優(yōu)解中也包含著其子問題的最優(yōu)解。（用反證法）分析問題是否滿足最優(yōu)性原理：先假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題的解不是最優(yōu)的;然后再證明在這個(gè)假設(shè)下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導(dǎo)致矛盾。

動(dòng)態(tài)規(guī)劃法設(shè)計(jì)算法一般分成三個(gè)階段：（1）分段：將原問題分解為若干個(gè)相互重疊的子問題；（2）分析：分析問題是否滿足最優(yōu)性原理，找出動(dòng)態(tài)規(guī)劃函數(shù)的遞推式；（3）求解：利用遞推式自底向上計(jì)算，實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃過程。動(dòng)態(tài)規(guī)劃法利用問題的最優(yōu)性原理，以自底向上的方式從子問題的最優(yōu)解逐步構(gòu)造出整個(gè)問題的最優(yōu)解。用動(dòng)態(tài)規(guī)劃法求解

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

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

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

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

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

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

0例如，有5個(gè)物品，其重量分別是{2,2,6,5,4}，價(jià)值分別為{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個(gè)物品，確定在各種情況下的背包能夠得到的最大價(jià)值；第二階段，只裝入前2個(gè)物品，確定在各種情況下的背包能夠得到的最大價(jià)值；依此類推，直到第n個(gè)階段。最后，V(n,C)便是在容量為C的背包中裝入n個(gè)物品時(shí)取得的最大價(jià)值。為了確定裝入背包的具體物品，從V(n,C)的值向前推，如果V(n,C)>V(n-1,C)，表明第n個(gè)物品被裝入背包，前n-1個(gè)物品被裝入容量為C-wn的背包中；否則，第n個(gè)物品沒有被裝入背包，前n-1個(gè)物品被裝入容量為C的背包中。依此類推，直到確定第1個(gè)物品是否被裝入背包中為止。由此，得到如下函數(shù)：

（式6.13）

回溯法

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

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

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

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

對(duì)物品1的選擇對(duì)物品3的選擇對(duì)物品2的選擇1111110000000112345781112141531069解空間樹的動(dòng)態(tài)搜索（1）

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

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

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