摘要回溯法是算法設(shè)計(jì)的根本方法之一,又稱“通用解題法〞。使用回溯法可以系統(tǒng)地搜索所給問(wèn)題的一個(gè)解或全部解。它適用于求解一些涉及到尋找一組解的問(wèn)題或者求滿足某些約束條件的最優(yōu)解問(wèn)題,且適用于求解組合數(shù)量較大的問(wèn)題。行業(yè)、各領(lǐng)域都廣泛采用了計(jì)算機(jī)信息技術(shù)，并由此產(chǎn)生出開(kāi)發(fā)各種應(yīng)用軟件的需求。為了以最小的本錢、最快的速度、最好的質(zhì)量開(kāi)發(fā)出適合各種應(yīng)用需求的軟件，必須遵循軟件工程的原那么。設(shè)計(jì)一個(gè)高效的程序不僅需要編程小技巧，更需要合理的數(shù)據(jù)組織和清晰高效的素算法，這正是計(jì)算機(jī)科學(xué)領(lǐng)域數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)所研究的主要內(nèi)容。因此,了解回溯法的根本思想與解題步驟對(duì)解決結(jié)合0-1背包問(wèn)題介紹了回溯法的根本思想和解題步驟,并在C++6.0環(huán)境下驗(yàn)證了回溯法可以有效地解決0-1背包問(wèn)題。關(guān)鍵詞：回溯法，背包問(wèn)題目錄TOC\o"1-8"\h\z\u1問(wèn)題描述12問(wèn)題分析23建立數(shù)學(xué)模型34算法設(shè)計(jì)45算法實(shí)現(xiàn)56測(cè)試分析8結(jié)論9參考文獻(xiàn)101問(wèn)題描述對(duì)于0-1背包問(wèn)題回溯法的一個(gè)實(shí)例，n=4，c=7，p=[9,10,7,4],w=[3,5,2,1].這4個(gè)物品的單位重量?jī)r(jià)值分別為[3,2,3,5,4].以物品為單位價(jià)值的遞減序裝入物品。先裝入物品4，然后裝入物品3和1.裝入這3個(gè)物品后，剩余的背包容量為1，只能裝入0.2的物品2.由此可得到一個(gè)解為x=[1,0,2,1,1],其相應(yīng)的價(jià)值為22.盡管這不是一個(gè)可行解，但可以證明其價(jià)值是最有大的上界。因此，對(duì)于這個(gè)實(shí)例，最優(yōu)值不超過(guò)22.回溯法的根本思想是按深度優(yōu)先策略，從根節(jié)點(diǎn)出發(fā)搜索解空間樹(shù)，算法搜索至解空間的任一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解，如果肯定不包含，那么跳過(guò)以該結(jié)點(diǎn)為根的子樹(shù)的搜索，逐層向其祖先結(jié)點(diǎn)回溯，否那么，進(jìn)入該子樹(shù)，繼續(xù)按深度優(yōu)先進(jìn)行搜索。2問(wèn)題分析利用回溯法的設(shè)計(jì)思想來(lái)解決背包問(wèn)題。首先是將可供選擇的物品的個(gè)數(shù)輸入程序，將物品排成一列，計(jì)算總物品的體積s，然后輸入背包的實(shí)際體積V，如果背包的體積小于0或者大于物品的總體積s，那么判斷輸入的背包體積錯(cuò)誤，否那么開(kāi)始順序選取物品裝入背包，假設(shè)已選取了前i件物品之后背包還沒(méi)有裝滿，那么繼續(xù)選取第i+1件物品，假設(shè)該件物品"太大"不能裝入，那么棄之而繼續(xù)選取下一件，直至背包裝滿為止。但如果在剩余的物品中找不到適宜的物品以填滿背包，那么說(shuō)明"剛剛"裝入背包的那件物品"不適宜"，應(yīng)將它取出"棄之一邊"，繼續(xù)再?gòu)?它之后"的物品中選取，如此重復(fù)，直至求得滿足條件的解。因?yàn)榛厮萸蠼獾囊?guī)那么是"后進(jìn)先出"，所以要用到棧來(lái)存儲(chǔ)符合條件的解，在存儲(chǔ)過(guò)程中，利用數(shù)組來(lái)存儲(chǔ)各個(gè)物品的體積，然后用深度優(yōu)先的搜索方式求解，將符合條件的數(shù)組元素的下標(biāo)存入棧里，最后得到符合條件的解并且實(shí)現(xiàn)輸出。3建立數(shù)學(xué)模型0-l背包問(wèn)題是子集選取問(wèn)題。一般情況下，0-1背包問(wèn)題是NP難題。0-1背包問(wèn)題的解空間可用子集樹(shù)表示。解0-1背包問(wèn)題的回溯法與裝載問(wèn)題的回溯法十分類似。在搜索解空間樹(shù)時(shí)，只要其左兒子結(jié)點(diǎn)是一個(gè)可行結(jié)點(diǎn)，搜索就進(jìn)入其左子樹(shù)。當(dāng)右子樹(shù)有可能包含最優(yōu)解時(shí)才進(jìn)入右子樹(shù)搜索。否那么將右子樹(shù)剪去。設(shè)r是當(dāng)前剩余物品價(jià)值總和；cp是當(dāng)前價(jià)值；bestp是當(dāng)前最優(yōu)價(jià)值。當(dāng)cp+r≤bestp時(shí)，可剪去右子樹(shù)。計(jì)算右子樹(shù)中解的上界的更好方法是將剩余物品依其單位重量?jī)r(jià)值排序，然后依次裝入物品，直至裝不下時(shí)，再裝入該物品的一局部而裝滿背包。由此得到的價(jià)值是右子樹(shù)中解的上界。算法復(fù)雜性是算法運(yùn)行所需要的計(jì)算機(jī)資源的量，需要時(shí)間資源的量稱為時(shí)間復(fù)雜性，需要的空間資源的量稱為空間復(fù)雜性。這個(gè)量應(yīng)該只依賴于算法要解的問(wèn)題的規(guī)模、算法的輸入和算法本身的函數(shù)。如果分別用N、I和A表示算法要解問(wèn)題的規(guī)模、算法的輸入和算法本身，而且用C表示復(fù)雜性，那么，應(yīng)該有C=F(N,I,A)。一般把時(shí)間復(fù)雜性和空間復(fù)雜性分開(kāi)，并分別用T和S來(lái)表示，那么有：T=T(N,I)和S=S(N,I)。最壞情況下的時(shí)間復(fù)雜性：最好情況下的時(shí)間復(fù)雜性：平均情況下的時(shí)間復(fù)雜性：其中DN是規(guī)模為N的合法輸入的集合；I*是DN中使T(N,I*)到達(dá)Tmax(N)的合法輸入；是中使T(N,)到達(dá)Tmin(N)的合法輸入；而P(I)是在算法的應(yīng)用中出現(xiàn)輸入I的概率。4算法設(shè)計(jì)使用棧作為該程序的數(shù)據(jù)結(jié)構(gòu)，利用棧進(jìn)行語(yǔ)法檢查，以深度優(yōu)先的搜索方式解空間，實(shí)現(xiàn)遞歸過(guò)程和函數(shù)的調(diào)用，在設(shè)計(jì)時(shí)還使用C語(yǔ)言的數(shù)組及其循環(huán)語(yǔ)言來(lái)實(shí)現(xiàn)程序。運(yùn)用回溯法解題，在搜索解空間樹(shù)時(shí)，只要其左兒子節(jié)點(diǎn)是一個(gè)可行結(jié)點(diǎn)，搜索就進(jìn)入左子樹(shù)，在右子樹(shù)中有可能包含最優(yōu)解是才進(jìn)入右子樹(shù)搜索。否那么將右子樹(shù)剪去。具體步驟如下：

1.針對(duì)所給問(wèn)題，定義問(wèn)題的解空間；2.確定易于搜索的解空間結(jié)3.以深度優(yōu)先的方式搜索解空間，并且在搜索過(guò)程中用剪枝函數(shù)防止無(wú)效搜索；5算法實(shí)現(xiàn)運(yùn)用Pc機(jī)，C/C++程序?qū)W習(xí)系統(tǒng)軟件編程C語(yǔ)言程序源代碼#include<stdio.h>#definesize20structstacks{

intdata[size];

inttop;}stack;voidmain(){

intw[size];

intV;

intk=0;

inti=0;

intj=1;

intnumber;

ints=0;

printf("\n請(qǐng)輸入可供選擇裝入物品的個(gè)數(shù)：");

scanf("%d",&number);

printf("\n請(qǐng)輸入各件物品的體積：");

for(i=0;i<number;i++)

scanf("%d",&w[i]);

for(i=0;i<number;i++)

s=s+w[i];

printf("\n可供選擇的物品的總體s=%d\n",s);

printf("\n請(qǐng)輸入背包的總體積：");

scanf("%d",&V);

if(V<0||V>s)

printf("\n輸入背包體積錯(cuò)誤");

printf("\n");

for(i=0;i<number;i++)

stack.data[i]=0;

stack.top=0;

do

{

while(V>0&&k<=number)

{

if(V>=w[k])

{

stack.data[stack.top]=k;

stack.top++;

V-=w[k];

}

k++;

}

if(V==0)

{

printf("第%d個(gè)符合條件的解：",j);

for(i=0;i<stack.top;i++)

{printf("%d",w[stack.data[i]]);

}

j++;

printf("\n");

}

k=stack.data[--stack.top];

stack.data[stack.top]=0;

V+=w[k];

k++;}while(!(stack.top==0&&k==number));}6測(cè)試分析1.當(dāng)輸入的背包體積V小于物品的總體積s時(shí)：2.當(dāng)輸入的背包體積V大于物品的總體積s時(shí)：當(dāng)輸入的背包體積小于等于可供選擇的物品的總體積時(shí)，可以正確進(jìn)行選擇裝入的物品，并且統(tǒng)計(jì)符合條件的解的方法；當(dāng)輸入的背包體積小于0或者大于可供選擇的物品的總體積時(shí)，程序會(huì)自動(dòng)提醒輸入背包體積錯(cuò)誤，這樣就方便了程序的正確運(yùn)行與解決實(shí)際問(wèn)題的重要作用。圖6.1圖6.2結(jié)論本程序利用回溯法的設(shè)計(jì)思想來(lái)解決問(wèn)題，在用來(lái)求問(wèn)題的所有解時(shí)，針對(duì)所給問(wèn)題，定義問(wèn)題的解空間，確定易于搜索的解空間結(jié)構(gòu)，要回溯到根，且根結(jié)點(diǎn)的所有子樹(shù)都已被搜索遍才結(jié)束，回溯法的求解規(guī)那么是后進(jìn)先出，所以在程序設(shè)計(jì)中自然要使用到了棧。在程序設(shè)計(jì)過(guò)程中，更加穩(wěn)固了我的C語(yǔ)言程序設(shè)計(jì)根底知識(shí)，使我對(duì)C語(yǔ)言的循環(huán)操作和指針、數(shù)組操作更加熟悉，區(qū)別了棧與鏈表，學(xué)會(huì)用棧來(lái)解決實(shí)際問(wèn)題，并且聯(lián)系了樹(shù)的重要內(nèi)容，重點(diǎn)訓(xùn)練了對(duì)算法與數(shù)據(jù)結(jié)構(gòu)的難點(diǎn)內(nèi)容，算法與數(shù)據(jù)結(jié)構(gòu)的統(tǒng)一，使編程語(yǔ)言更加簡(jiǎn)潔，清晰易懂，強(qiáng)調(diào)了好的程序設(shè)計(jì)風(fēng)格,運(yùn)行結(jié)果更加美觀，在調(diào)試和運(yùn)行時(shí)，我遇到了一些很根底的問(wèn)題，通過(guò)請(qǐng)教老師和同學(xué)，這些問(wèn)題都逐一解決了，這使得我在運(yùn)行正確通過(guò)時(shí)，內(nèi)心產(chǎn)生了一種很強(qiáng)烈的成就感，因此提高了我對(duì)編程的濃厚興趣，更加增強(qiáng)了自己學(xué)習(xí)好計(jì)算機(jī)語(yǔ)言的信心。參考文獻(xiàn)[1]黃迪明，余勤等編著.

C語(yǔ)言程序設(shè)計(jì)教程[M].國(guó)防工業(yè)出版社1999.[2]陳媛等編