用c語言解決背包問題正文

1初步實現(xiàn)了設計目標，并且經(jīng)過適當完善后，將可以應用在實際生活中。本課程設計是為了解決旅行者的背包問題。將分別采用枚舉；回來實現(xiàn)程序。研究應用遞歸思想，背包算法。應用數(shù)據(jù)結(jié)構(gòu)基礎知識進行實際分析。編程實現(xiàn)算法。2本課程設計采用枚舉，回溯，動態(tài)規(guī)劃三種方法解決常見的背包問題。例如入左子樹，在右子樹可能包含最優(yōu)解是才進入右子樹搜索。否則將右子樹剪去。具體步驟如下：（1）針對所給問題，定義問題的解空間；（3）以深度優(yōu)先的方式搜索解空間，并且在搜索過程中用剪枝函數(shù)避免無效搜索。在課程設計中，系統(tǒng)開發(fā)平臺為windowsxp，關棧方面的知識。棧（Stack）是限制僅在表的一端進行插入和刪除運算的線性表。當用一維數(shù)組存儲棧時，被稱為順序棧。（Bottom(2)當表中沒有元素時稱為空棧，用Top=(3)棧為后進先出（LastInFirstOut）的線性表，簡稱為LIFO表。3最新"的元素，即最后插入（進棧）的元素，而最先插入的是被放在棧的底部，要到最后才能刪除。棧為后進先出（LastInFirstOut）的線性表，簡稱為LIFO表。棧的修后才能刪除。流程圖如下：棧的基本運算：（1）InitStack（S）（3）StackFull（S）注意：該運算只適用于棧的順序存儲結(jié)構(gòu)。退棧。若棧S非空，則將S的棧頂元素刪去，并返回該元素。（6）StackTop（S）4取棧頂元素。若棧S非空，則返回棧頂元素，但不改變棧的狀態(tài)。回溯法也稱為試探法，該方法首先暫時放棄關于問題規(guī)模大小的限制，候選解滿足包括問題規(guī)模在內(nèi)的所有要求時，該候選解就是問題的一個解。在回溯法中，放棄當前候選解，尋找下一個候選解的過程稱為回溯。它適用于解一些組合數(shù)較大的問題。高搜索的效率，即啟發(fā)式的搜索?？捎没厮莘ㄇ蠼獾膯栴}P，通常要能表達為：對于已知的由n元組5明無解。解問題P的最樸素的方法就是枚舉法，即對E中的所有n元組逐一地檢測其是否滿足D的全部約束，若滿足，則為問題P的一個解。但顯然，其計算量是相當大的。我們發(fā)現(xiàn)，對于許多問題，所給定的約束集D具有完備性，即i元組用這類問題的上述性質(zhì)而提出來的比枚舉法效率更高的算法。6否否否是否是本算法采用先進后出的算法來一個一個測試可行的全部解，所以很顯然要用到棧。我通過建立順序表來錄入我要輸入的各個物體的體積，然后通過sum比我預定的目標體積小，那就繼續(xù)入棧，有合適的組合則輸出，否則說明剛才選入的物體體積即棧最頂端的那個不適合導致后面沒有合適的解，所做棧底的所有情況滿足后，我們就要考慮以第二個物體為棧底的情況，其實我并沒有把第一個物體出棧，只是我讀的時候把第一個物體“屏蔽”了，也就是說它雖然在棧中，但是我不考慮它，而是考慮新的棧也就是總棧中截取的7那么就沒有物體可以作為參數(shù)入棧或出棧了，所有循環(huán)結(jié)束。本算法采用3重while循環(huán)嵌套來實現(xiàn)算出所有不重復的解。typedefstruct{}seqlist;typedefstruct{}seqstack;{s=newseqstack;//{printf("空間不足");//若無法生成結(jié)構(gòu)體，則輸出“空間不足”8{s->top=-1;//}{if(s->top==-1)}intpush_seqstack(seqlist*l,inti,seqstack*s){return0;//棧滿，無{s->data[s->top]=i;s->sum=s->sum+l->data[i];9}{return0;//?？?，無元{*x=s->data[s->top];s->sum=s->sum-l->data[s->data[s->top]];/s->top--;//棧內(nèi)元素個數(shù)減1}}{seqlist*l;intx=1;l=newseqlist;//\n------------------\n"scanf("%d",&x);while(x!=0)//輸入元素不為{l->last++;//沒輸入}}程序調(diào)試成功。在課程設計代碼調(diào)試過程中也出了不少差錯，比如頭文件很容易忽略，同學指出才發(fā)現(xiàn)；一些符號，像“；”也很容易拉克服了。在此過程中我學到了不少調(diào)試的技巧，極大得豐富了編程的知識，這些在程序的優(yōu)化方面幫助很大。通過此次課程設計的實踐，感觸較深。不僅使我加深了對書本知識的理解，而且鍛煉了我編寫程序、調(diào)試程序的能力，學習文檔編寫規(guī)范，培養(yǎng)獨立學習、地方考慮的還不夠周到。在本課題中，我們研究了如何用遺傳算法求解組合優(yōu)化問題中的背包問題，背包問題是一個典型的組合優(yōu)化問題，在計算理論中屬于NP-完全問題，其計算復雜度為，傳統(tǒng)上采用動態(tài)規(guī)劃來求解。背包問題就是在資源有限的條件下，是我們將來的學習中需要改進和加強的地方?，F(xiàn)出棧，所以也算是其中的遺憾。源程序代碼：{{intw[size];intV;intk=0;inti=0;intj=1;printf("\n請輸入可供選擇裝入物品的個數(shù)：");printf("\n請輸入各件物品的體積：");printf("\n可供選擇的物品的總體printf("\n請輸入背包的總體積：");printf("\n輸入背包體積錯誤");printf("\n");{{{}}{printf("第%d個符合條件的解：",j);{}j++;printf("\n");}k=stack.data[--stack.to}Abstract:Basedonthecomprehensiveanalysisontheplasticpart’sstructuresermoundingqualityandmouldmenufactoringsidecorepullingwasdesigned.Byadoptingthcore-pulling.Acorrespondinginjectionmworkingprocessofthemouldwasintroduced在程序中，可能需要為某些整數(shù)定義一個別名，我們可以利用預處理指令#define來完成這項工作，您的代碼可能是：{(1)枚舉型是一個集合，集合中的元素(枚舉成員)是一些命名的整型常量，元素之間用逗號,隔開。(2)DAY是一個標識符，可以看成這個集合的名字，是一個可選項，即是可有可無的項。(4)可以人為設定枚舉成員的值，從而自定義某個范圍內(nèi)的整數(shù)。(5)枚舉型是預處理指令#define的替代。(6)類型定義以分號;結(jié)束。新的數(shù)據(jù)類型定義完成后，它就可以使用了。我們已經(jīng)見過最基本的數(shù)據(jù)類型，如：整型int,單精度浮點型float,數(shù)據(jù)類型聲明變量通常是這樣：doubleresult;/既然枚舉也是一種數(shù)據(jù)類型，那么它和基本數(shù)據(jù)類型一樣也可以對變量進行聲明。{enumDAYtomorrow;//變enumDAYgood_day,bad_day;//變方法二：類型定義與變量聲明同時進行：enum//跟第一個定義不同的是，此處的標號DAY省略，這是允許的。{enumweek{Mon=1,Tue,Wed,Thu,FriSat,Sun}days;//變量days的類型為枚舉型enumweekenumBOOLEAN{false,true}end_flag,match_flag;//定義枚舉類型并聲明了兩個枚舉型變量方法三：用typedef關鍵字將枚舉類型定義成別名，并利用該別名進行變量聲明：typedefenumworkday{workdaytoday,tomorrow;//變量today和tomorrow的類型為枚舉型workday，也即enumtypedefenum{workdaytoday,tomorrow;//變量today和tomorrow的類型為枚舉型workday，也即enum也可以用這種方式：typedefenumworkday{workdaytoday,tomorrow;//變量today和tomorrow的類型為枚舉型workday，也即enum量。錯誤示例如下所示：typedefenum{typedefenumWEEK{typedefenum{typedefenumWEEK{3.1對枚舉型的變量賦值。實例將枚舉類型的賦值與基本數(shù)據(jù)類型的賦值進行了對比：{enumDAYyesterday,today,printf("%d%d%d\n",yesterday,today,tomorrow);}{intx=10,y=20,z=30;printf("%d%d%d\n",yesterday,today,tomorrow);}方法三：定義類型的同時聲明變量，然后對變量賦值。/*定義枚舉類型，同時聲明該類型的三個{printf("%d%d%d\n",x,y,z);//輸出：10printf("%d%d%d\n",yesterday,today,tomorrow);//輸出：123}方法四：類型定義，變量聲明，賦初值同時進行。/*定義枚舉類型，同時聲明該類型的三個變量，并賦{}yesterday=MON,today=TUE,tomorrow=WE{printf("%d%d%d\n",x,y,z);//輸出：10printf("%d%d%d\n",yesterday,today,tomorrow);//輸出：123}3.2對枚舉型的變量賦整數(shù)值時，需要進行類型轉(zhuǎn)換。{enumDAYyesterday,today,tomorrow=(enumDAY)30;////tomorrow=3;//錯誤printf("%d%d%d\n",yesterday,today,tomorrow);//輸出：2330}{NEWLINEVTAB='\r',{charstr[]="I'mElyefod";countofletter++;{countofspace++;}printf("%s%dtimes%c",match_flag?"mprintf("countofletters:%d%c%c",countofletter,NEWLINE,RETURN);}輸出：{NEWLINEVTAB='\r',='\n',='\v',{printf("%dbytes\n",sizeof(enumescapes));//4bytesprintf("%dbytes\n",sizeof(escapes));//4bytesprintf("%dbytes\n",sizeof(enumBOOLEAN));//4bytesprintf("%dbytes\n",sizeof(BOOLEAN));//4byte