算法設(shè)計(jì)試驗(yàn)報(bào)告

華北電力大學(xué)驗(yàn)報(bào)告實(shí)驗(yàn)名稱算法設(shè)計(jì)與分析綜合實(shí)驗(yàn)課程名稱算法設(shè)計(jì)與分析專業(yè)班級(jí):學(xué)生姓名:學(xué)號(hào):成績(jī):指導(dǎo)教師:實(shí)驗(yàn)日期:華北電力大學(xué)實(shí)驗(yàn)報(bào)告[綜合實(shí)驗(yàn)一]分治策略一歸并排序一、實(shí)驗(yàn)?zāi)康募耙髿w并排序是一個(gè)非常優(yōu)秀的排序方法,也是典型的分治策略的典型應(yīng)用。實(shí)驗(yàn)要求：(1)編寫一個(gè)模板函數(shù)：template<typenameT>，MergeSort(T*a,intn);以及相應(yīng)的一系列函數(shù)，采用分治策略，對(duì)任意具有:booloperator<(constT&x,constT&y);比較運(yùn)算符的類型進(jìn)行排序。(2)與STL庫(kù)中的函數(shù)std::sort(..)進(jìn)行運(yùn)行時(shí)間上的比較，給出比較結(jié)果，如：動(dòng)態(tài)生成100萬(wàn)個(gè)隨機(jī)生成的附點(diǎn)數(shù)序列的排序列問(wèn)題，給出所用的時(shí)間比較。二、所用儀器、設(shè)備計(jì)算機(jī)、VisualC++軟件。三、實(shí)驗(yàn)原理分治原理：分治算法的基本思想是將一個(gè)規(guī)模為N的問(wèn)題分解為K個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題相互獨(dú)立且與原問(wèn)題性質(zhì)相同。求出子問(wèn)題的解，就可得到原問(wèn)題的解。當(dāng)我們求解某些問(wèn)題時(shí)，由于這些問(wèn)題要處理的數(shù)據(jù)相當(dāng)多，或求解過(guò)程相當(dāng)復(fù)雜，使得直接求解法在時(shí)間上相當(dāng)長(zhǎng)，或者根本無(wú)法直接求出。對(duì)于這類問(wèn)題，我們往往先把它分解成幾個(gè)子問(wèn)題，找到求出這幾個(gè)子問(wèn)題的解法后，再找到合適的方法，把它們組合成求整個(gè)問(wèn)題的解法。如果這些子問(wèn)題還較大，難以解決，可以再把它們分成幾個(gè)更小的子問(wèn)題，以此類推，直至可以直接求出解為止。這就是分治策略的基本思想。歸并原理：歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法(DivideandConquer)的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。四、實(shí)驗(yàn)方法與步驟歸并過(guò)程為：比較a[i]?a[j]的大小，若a[i]Wa[j]，則將第一個(gè)有序表中的元素a[i]復(fù)制到r[k]中，并令i和k分別加上1；否則將第二個(gè)有序表中的元素a[j]復(fù)制到r[k]中，并令j和k分別加上1，如此循環(huán)下去，直到其中一個(gè)有序表取完，然后再將另一個(gè)有序表中剩余的元素復(fù)制到r中從下標(biāo)k到下標(biāo)t的單元。歸并排序的算法我們通常用遞歸實(shí)現(xiàn)，先把待排序區(qū)間[s,t]以中點(diǎn)二分，接著把左邊子區(qū)間排序，再把右邊子區(qū)間排序，最后把左區(qū)間和右區(qū)間用一次歸并操作合并成有序的區(qū)間[s,t]。實(shí)現(xiàn)時(shí)間計(jì)量：#define_CLOCK_T_DEFINEDsrand((unsigned)time(0));〃定義一數(shù)組a[n];對(duì)每一個(gè)賦予一值。a[i]=rand();得到隨即數(shù)。duration=(double)(finish-start)/CLOCKS_PER_SEC;start=clock();將系統(tǒng)時(shí)間賦予Start。以便以后進(jìn)行比較。std::sort(b,b+1000);系統(tǒng)執(zhí)行1000個(gè)數(shù)據(jù)。Finish-Start為最終結(jié)果。五、實(shí)驗(yàn)結(jié)果與數(shù)據(jù)處理實(shí)驗(yàn)結(jié)果截圖：第頁(yè)共頁(yè)華北電力大學(xué)實(shí)驗(yàn)報(bào)告輸外元匕顯，」：；儀年序方世:1.回升JI,于 之.￡t曲疔T7.570T3178.21rS42.039812.2311535.3125a51738111932582246712G253.127234.530062132255109.4 775.26333210477G3329859.5211G8&.T7.570T3178.21rS42.039812.2311535.3125a51738111932582246712G253.127234.530062132255109.4 775.26333210477G3329859.5211G8&.1128G7,H17455.41978872Z83S.?2&2GS,727654.635331281S￡.581044181208713日63T17754.519874S23.&9 11SG.&14424.7 51E5383299.5910461512090.313656.】1773092Q02571l&q.37 1421.77 1S97.38ZZT&&8417.9710542.35533923883.316590.7G7436 6944.77889S.43 3^45211G635.G 11O97.ti1￡1S712255.1 123&7.312511.6143Z8,3 14SG5,T15283.2 16031.11T8283 18454.2 18729.1 19QE0.22009G 2Q43G.S2G490.G2376652453324640.924?fi6.224839.22&G30,326726,22$74G.32&7SS,1ZS3G&.4 2S3S9TZS439.9 237583046630302232511.7 3271952889S221Q312491G.831304531465.431q69331747.9-M22G17e+037293971322029std：： /：Otiis輸入需要顯示的排序方法：std：： /：Otiis輸入需要顯示的排序方法：1,歸并排序 Z.std排序0Pres&anykeytoeoritinue日一退出第頁(yè)共頁(yè)華北電力大學(xué)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)代碼：#include<iostream.h>#include<algorithm>#include<time.h>#include<stdio.h>#include<stdlib.h>usingnamespacestd;template<classType>voidMergSort(Typea[],intn){Type*b=newType[n];ints=1;while(s<n){MergPass(a,b,s,n);s+=s;MergPass(b,a,s,n);s+=s;))template<classType>voidMergPass(Typex[],Typey[],ints,intn){inti=0;while(i<=n-2*s){Merg(x,y,i,i+s-1,i+2*s-1);i=i+2*s;第頁(yè)共頁(yè)華北電力大學(xué)實(shí)驗(yàn)報(bào)告if(i+s<n)Merg(x,y,i,i+s-1,n-1);else{for(intj=i;j<=n-1;j++){y[j]=x[j];)))template<classType>voidMerg(Typec[],Typed[],intl,intm,intr){inti=l,j=m+1,k=l;while((i<=m)&&(j<=r)){if(c[i]<=c[j])d[k++]=c[i++];elsed[k++]=c[j++];)if(i>m)for(intq=j;q<=r;q++)d[k++]=c[q];elsefor(intq=i;q<=m;q++)d[k++]=c[q];)floatrandf(floatbase,floatup){return(rand()%(int)((up-base)*RAND_MAX))/(float)RAND_MAX;//產(chǎn)生隨機(jī)數(shù))voidprintArray(float*a,intN){for(inti=0;i<=N;i++){if((i%8==0)&&(i>0)){cout<<a[i]<<endl;)else{cout<<a[i]<<"";)))voidmain(){intArrayLen=5;cout<<"請(qǐng)輸入元素個(gè)數(shù)："<<endl;cin>>ArrayLen;float*array=newfloat[ArrayLen];float*arrays=newfloat[ArrayLen];floatmn,ene;第頁(yè)共頁(yè)華北電力大學(xué)實(shí)驗(yàn)報(bào)告printf("數(shù)組已建立： \n");srand((unsigned)time(NULL));〃設(shè)置隨機(jī)數(shù)的seedfor(inti=0;i<ArrayLen;i++)(mn=(float)rand();〃產(chǎn)生小數(shù)ene=randf(1,10000)+mn;arrays[i]=ene;array[i]=ene;)〃cout<<"需要排序的歸并數(shù)組:\n";//printArray(array,ArrayLen);intflag=1;while(flag!=0){cout<<"\n輸入需要顯示的排序方法："<<endl;cout<<"1.歸并排序2.std排序0.退出"<<endl;cin>>flag;switch(flag){case0:break;case1:{clock_ts=0,e=0;s=clock();MergSort(array,ArrayLen);e=clock();//cout<<"排序后的序列為："<<endl;//printArray(array,ArrayLen);cout<<"\nMergSort運(yùn)行了："<<(e-s)<<"ms"<<endl;break;)case2:{clock_tstart1=0,end1=0;start1=clock();std::sort(&arrays[0],&arrays[ArrayLen]);end1=clock();//printArray(array,ArrayLen);cout<<"\nstd::sort運(yùn)行了："<<(end1-start1)<<"ms"<<endl;break;))))第頁(yè)共頁(yè)華北電力大學(xué)實(shí)驗(yàn)報(bào)告［綜合實(shí)驗(yàn)二］貪心算法一［綜合實(shí)驗(yàn)二］貪心算法一Huffman樹及Huffman編碼一、實(shí)驗(yàn)?zāi)康募耙笠粋€(gè)記錄字符及出現(xiàn)頻率的文件如下所示：huffman.haf7a,45b,13c,12d,16e,89f,34g,20試編寫一個(gè)讀取此種格式文件類CHuffman,內(nèi)部機(jī)制采用優(yōu)先隊(duì)列，用于建立Huffman樹及進(jìn)行Huffman編碼輸出，其用法可以如下所示：CHuffmanhm("huffman.dat");hm.CreateTree();hm.OutputTree();hm.OutputCode();〃二進(jìn)制形式的字符串對(duì)于輸出樹的形式可自行決定(如圖形界面或字符界面)。二、所用儀器、設(shè)備計(jì)算機(jī)、VisualC++軟件。三、實(shí)驗(yàn)原理貪心原理：⑴隨著算法的進(jìn)行，將積累起其它兩個(gè)集合：一個(gè)包含已經(jīng)被考慮過(guò)并被選出的候選對(duì)象，另一個(gè)包含已經(jīng)被考慮過(guò)但被丟棄的候選對(duì)象。⑵有一個(gè)函數(shù)來(lái)檢查一個(gè)候選對(duì)象的集合是否提供了問(wèn)題的解答。該函數(shù)不考慮此時(shí)的解決方法是否最優(yōu)。⑶還有一個(gè)函數(shù)檢查是否一個(gè)候選對(duì)象的集合是可行的，也即是否可能往該集合上添加更多的候選對(duì)象以獲得一個(gè)解。和上一個(gè)函數(shù)一樣，此時(shí)不考慮解決方法的最優(yōu)性。⑷選擇函數(shù)可以指出哪一個(gè)剩余的候選對(duì)象最有希望構(gòu)成問(wèn)題的解。(5)最后，目標(biāo)函數(shù)給出解的值。(6)為了解決問(wèn)題，需要尋找一個(gè)構(gòu)成解的候選對(duì)象集合，它可以優(yōu)化目標(biāo)函數(shù)，貪婪算法一步一步的進(jìn)行。起初，算法選出的候選對(duì)象的集合為空。接下來(lái)的每一步中，根據(jù)選擇函數(shù)，算法從剩余候選對(duì)象中選出最有希望構(gòu)成解的對(duì)象。如果集合中加上該對(duì)象后不可行，那么該對(duì)象就被丟棄并不再考慮；否則就加到集合里。每一次都擴(kuò)充集合，并檢查該集合是否構(gòu)成解。如果貪婪算法正確工作，那么找到的第一個(gè)解通常是最優(yōu)的。Huffman原理：給定n個(gè)權(quán)值作為n的葉子結(jié)點(diǎn)，構(gòu)造一棵二叉樹，若帶權(quán)路徑長(zhǎng)度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffman1^?)。哈夫曼樹是帶權(quán)路徑長(zhǎng)度最短的樹，權(quán)值較大的結(jié)點(diǎn)離根較近。第頁(yè)共頁(yè)華北電力大學(xué)實(shí)驗(yàn)報(bào)告四、實(shí)驗(yàn)方法與步驟哈夫曼算法以自底向上的方式構(gòu)造表示最優(yōu)前綴碼的二叉樹T。算法以個(gè)葉結(jié)點(diǎn)開始，執(zhí)行次的〃合并〃運(yùn)算后產(chǎn)生最終所要求的樹T。給定編碼字符集C及其頻率分布f，即C中任一字符c以頻率f(c)在數(shù)據(jù)文件中出現(xiàn)。C的一個(gè)前綴碼編碼方案對(duì)應(yīng)于一棵二叉樹T。字符c在樹T中的深度記為。也是字符c的前綴碼長(zhǎng)。該編碼方案的平均碼長(zhǎng)定義為：B(丁)使平均碼長(zhǎng)達(dá)到最小的前綴碼編碼方案稱為C的一個(gè)最優(yōu)前綴碼。一旦兩棵具有最小頻率的樹合并后，產(chǎn)生的一顆新的樹，起頻率為合并的兩棵樹的頻率之和，并將新樹插入優(yōu)先隊(duì)列中。優(yōu)先隊(duì)列，優(yōu)先隊(duì)列是0個(gè)或多個(gè)元素的集合，每個(gè)元素都有一個(gè)優(yōu)先權(quán)或值,對(duì)優(yōu)先隊(duì)列執(zhí)行的操作有1)查找;2)插入一個(gè)新元素;3)刪除.在最小優(yōu)先隊(duì)列(minpriorityqueue)中，查找操作用來(lái)搜索優(yōu)先權(quán)最小的元素,刪除操作用來(lái)刪除該元素;對(duì)于最大優(yōu)先隊(duì)列(maxpriorityqueue),查找操作用來(lái)搜索優(yōu)先權(quán)最大的元素,刪除操作用來(lái)刪除該元素.優(yōu)先權(quán)隊(duì)列中的元素可以有相同的優(yōu)先權(quán)，查找與刪除操作可根據(jù)任意優(yōu)先權(quán)進(jìn)行.五、實(shí)驗(yàn)結(jié)果與數(shù)據(jù)處理主要代碼如下：Huffman::Huffman(char*sFileName1)(this->sFileName=sFileName1;ifstreamfin(sFileName);charch[4];fin.getline(ch,4);intn1=atoi(ch);cout<<"節(jié)點(diǎn)數(shù)目："<<n1<<endl;this->n=n1;this->t=newTHaffmanNode[2*n1-1];this->nNext=n1;charch1;for(inti=0;i<n1;i++)(fin.get(ch1);t[i].c=ch1;fin.ignore(100,',');fin.getline(ch,4);t[i].f=atoi(ch);)for(inti=0;i<n;i++)(cout<<t[i].c<<""<<t[i].f<<endl;)for(inti=0;i<n;i++)(t[i].idx=i;PQ.push(t[i]);)第頁(yè)共頁(yè)華北電力大學(xué)實(shí)驗(yàn)報(bào)告while(!PQ.empty())(if((PQ.size())>=2)(THaffmanNodenn,nr,nl;nl=PQ.top();PQ.pop();nr=PQ.top();PQ.pop();nn.f=nl.f+nr.f;nn.l=nl.idx;nn.r=nr.idx;nn.idx=nNext++;t[nl.idx].p=nn.idx;t[nr.idx].p=nn.idx;t[nn.idx]=nn;PQ.push(nn);)else(t[2*n-2].p=-1;break;)))Huffman::?Huffman(void)()voidHuffman::OutputTree()(for(inti=0;i<2*n-1;i++)(cout<<"權(quán)重："<<t[i].f<<"";cout<<"左孩子："<<t[i].l<<"";cout<<"右孩子："<<t[i].r<<"";cout<<"父節(jié)點(diǎn)："<<t[i].p<<"";cout<<"在數(shù)組的位置："<<t[i].idx<<endl;)〃現(xiàn)在數(shù)組中存的是哈弗曼數(shù))voidHuffman::OutputCode()(〃用stack來(lái)依次記錄各編碼的01編碼std::stack<int,std::list<int>>sk;第頁(yè)共頁(yè)

華北電力大學(xué)實(shí)驗(yàn)報(bào)告THaffmanNodentemp,ntempl;for(inti=0;i<n;i++)(ntemp=t[i];while(ntemp.p!=-1)(ntemp1=t[ntemp.p];if(t[ntemp1.l].idx==ntemp.idx)(sk.push(0);ntemp=ntemp1;)else(sk.push(1);ntemp=ntemp1;))inti1=sk.size();cout<<t[i].f<<"： ";for(inti=0;i<i1;i++)(cout<<sk.top();sk.pop();)cout<<endl;))實(shí)驗(yàn)結(jié)果截圖：的SSog目T節(jié)節(jié)節(jié)節(jié)節(jié)節(jié)日7的SSog目T節(jié)節(jié)節(jié)節(jié)節(jié)節(jié)日7乂父田rii［綜合實(shí)驗(yàn)三］用回溯方法求解n后問(wèn)題、實(shí)驗(yàn)?zāi)康募耙蟮陧?yè)共頁(yè)華北電力大學(xué)實(shí)驗(yàn)報(bào)告問(wèn)題：對(duì)任意給定的n求解n后問(wèn)題。具體要求：.封裝n后問(wèn)題為類，編寫以下兩種算法進(jìn)行求解：(1)遞歸回溯方法；(2)迭代回溯方法。(選).對(duì)任意給定的n,要求輸出其解向量(所有解)，并輸出其解數(shù);.構(gòu)造n后問(wèn)題的解數(shù)表格(由程序自動(dòng)生成)：n后數(shù)解數(shù)第一個(gè)解42(2,4,1,3)56二、所用儀器、設(shè)備計(jì)算機(jī)、VisualC++軟件。三、實(shí)驗(yàn)原理回溯原理：回溯算法也叫試探法，它是一種系統(tǒng)地搜索問(wèn)題的解的方法?；厮菟惴ǖ幕舅枷胧牵簭囊粭l路往前走，能進(jìn)則進(jìn)，不能進(jìn)則退回來(lái)，換一條路再試。用回溯算法解決問(wèn)題的一般步驟為：1、定義一個(gè)解空間，它包含問(wèn)題的解。2、利用適于搜索的方法組織解空間。3、利用深度優(yōu)先法搜索解空間。4、利用限界函數(shù)避免移動(dòng)到不可能產(chǎn)生解的子空間。問(wèn)題的解空間通常是在搜索問(wèn)題的解的過(guò)程中動(dòng)態(tài)產(chǎn)生的，這是回溯算法的一個(gè)重要特性。四、實(shí)驗(yàn)方法與步驟n后問(wèn)題等于在nXn格的棋盤上放置n個(gè)皇后，任何2個(gè)皇后不放在同一行或同一列或同一斜線上。即規(guī)定每一列放一個(gè)皇后，不會(huì)造成列上的沖突；當(dāng)?shù)趇行被某個(gè)皇后占領(lǐng)后，則同一行上的所有空格都不能再放皇后，要把以i為下標(biāo)的標(biāo)記置為被占領(lǐng)狀態(tài)。K：第K個(gè)皇后，也表示第K行X[i]：第K個(gè)皇后在第K行的第i列皇后k在第k行第x[k]列時(shí)，x[i]==x[k]時(shí)，兩皇后在同一列上;abs(x[i]-x[k])==abs(i-k)時(shí)，兩皇后在同一斜線上;兩種情況兩皇后都可相互攻擊，返回false表示不符合條件。五、實(shí)驗(yàn)結(jié)果與數(shù)據(jù)處理實(shí)驗(yàn)結(jié)果截圖：第頁(yè)共頁(yè)華北電力大學(xué)實(shí)驗(yàn)報(bào)告■"DAProgramFiles\VC++6.0\MSE科KKXX討有消型進(jìn)入皇后|4]WWHKMWM5KW請(qǐng)輸久里后數(shù) '"42^13，制…...?,，……肌3142…跳.一…#事…方案?jìng)€(gè)蚊I2是否繼續(xù)1T為是手。為否1請(qǐng)輸入皇后數(shù)5352M一件….…#…#一1叫芭53器……...tt.印.….…#??#??4135印.…器………悌一…幫5314，赭……幫…悌一心…?…機(jī)搜狗攜音輸入法至臼"J,"DeprogramFiles\VC++6,0\MSD?31425IL-鵬……胖.件…一，，村一.辨……唬,,B,W…#一件…一53142一一群■…，…沖.方案?jìng)€(gè)數(shù)，1。是否繼續(xù)？】為是，口為否實(shí)驗(yàn)代碼：#include<iostream.h>#include<math.h>classQueen(friendintnQueen(int);private:boolPlace(intk);voidBacktrack(intt);intn,*x; 〃當(dāng)前解longsum;〃當(dāng)前已找到的可行方案數(shù));boolQueen::Place(intk)(for(intj=1;j<k;j++)if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))returnfalse;returntrue;第頁(yè)共頁(yè)華北電力大學(xué)實(shí)驗(yàn)報(bào)告voidQueen::Backtrack(intt)(if(t>n)(sum++;〃達(dá)到葉結(jié)點(diǎn)for(inti=1;i<=n;i++)(cout<<x[i]<<"";)cout<<endl;for(i=1;i<=n;++i)(for(intj=1;j<=n;++j)(if(x[i]!=j)cout<<".";elsecout<<"#";)cout<<endl;)cout<<endl;)elsefor(inti=1;i<=n;i++){ 〃搜索子結(jié)點(diǎn)x[t]=i; //進(jìn)入第i個(gè)子結(jié)點(diǎn)if(Place(t))Backtrack(t+1);))intnQueen(intn){QueenX;〃初始化XX.n=n;X.sum=0;int*p=newint[n+1];for(inti=0;i<=n;i++)p[i]=0;X.x=p;X.Backtrack(1); 〃對(duì)整個(gè)解空間回溯搜索delete[]p;returnX.sum;)voidmain(){第頁(yè)共頁(yè)華北電力大學(xué)實(shí)驗(yàn)報(bào)告inta=0,b=0;cout<<歡迎進(jìn)入皇后問(wèn)題*********"<<endl;cout<<intflag=1;while(flag){cout<<"請(qǐng)輸入皇后數(shù)"<<endl;cin>>a;b=nQueen(a);cout<<”方案?jìng)€(gè)數(shù)："<<b<<endl;cout<<"是否繼續(xù)？1為是，0為否"<<endl;cin>>flag;))[綜合實(shí)驗(yàn)四]背包問(wèn)題的貪心算法[綜合實(shí)驗(yàn)四]背包問(wèn)題的貪心算法一、實(shí)驗(yàn)?zāi)康募耙髥?wèn)題：給定如下n種物品的編號(hào)，及其價(jià)值；背包重量為c,求最佳裝包方案，才能使其裝入背包的價(jià)值最大。物品編號(hào)12■■■n重量w[1]w[2]??w[n]價(jià)值v[1]v[2]■■■v[n]具體要求：將背包問(wèn)題進(jìn)行類的封裝；能對(duì)任意給定的n種物品的重量、價(jià)值及背包限重，輸出以上表格（或縱向輸出）；輸出背包問(wèn)題的解；本題要求采用STL庫(kù)中的排序算法數(shù)據(jù)進(jìn)行排序。二、所用儀器、設(shè)備計(jì)算機(jī)、VisualC++軟件。三、實(shí)驗(yàn)原理貪心算法解決背包問(wèn)題有幾種策略：（1）一種貪心準(zhǔn)則為：從剩余的物品中，選出可以裝入背包的價(jià)值最大的物品，利用這種規(guī)則，價(jià)值最大的物品首先被裝入（假設(shè)有足夠容量），然后是下一個(gè)價(jià)值最大的物品，如此繼續(xù)下去。這種策略不能保證得到最優(yōu)解。例如，考慮n=2,w=[100,10,10],p二[20,15,15],c=105。當(dāng)利用價(jià)值貪婪準(zhǔn)則時(shí)，獲得的解為x=[1,0,0]，這種方案的總價(jià)值為20。而最優(yōu)解為[0,1,1]，其總價(jià)值為30。（2）另一種方案是重量貪心準(zhǔn)則是：從剩下的物品中選擇可裝入背包的重量最小的物品。雖然這種規(guī)則對(duì)于前面的例子能產(chǎn)生最優(yōu)解，但在一般情況下則不一定能得到最優(yōu)解?？紤]n=2,w=[10,20],p=[5,100],c=25。當(dāng)利用重量貪婪策略時(shí)，獲得的解為x=[1,0],比最優(yōu)解[0,1]要差。（3）還有一種貪心準(zhǔn)則，就是我們教材上提到的，認(rèn)為，每一項(xiàng)計(jì)算yi=vi/si,即該項(xiàng)值和大小的比，再按比值的降序來(lái)排序，從第一項(xiàng)開始裝背包，然后是第二項(xiàng)，依次類推，盡可能的多放，直到裝滿背包。四、實(shí)驗(yàn)方法與步驟第頁(yè)共頁(yè)華北電力大學(xué)實(shí)驗(yàn)報(bào)告首先計(jì)算每種物品單位重量的價(jià)值Vi/Wi,然后依貪心選擇策略，將盡可能多的單位重量?jī)r(jià)值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超出C，則選擇單位重量?jī)r(jià)值次高的物品，并盡可能多的裝入背包。依此策略一直進(jìn)行下去，直到背包裝滿為止。采用貪婪準(zhǔn)則：每次選擇p/w最大的物品放入背包。注意在這之前的計(jì)算每種物品單位重量的價(jià)值Vi/Wi后，進(jìn)行排序。五、實(shí)驗(yàn)結(jié)果與數(shù)據(jù)處理實(shí)驗(yàn)截圖：31D:\PragramFiles\VC++6,0\MSDev98\Bin\.,.-口KSI請(qǐng)輸入物品的重量和價(jià)值： N清輸入第1個(gè)物品的重量和價(jià)值124府輸入第2個(gè)物品的重1量和價(jià)值235請(qǐng)輸入第3個(gè)物品的重量和價(jià)值354.5請(qǐng)輸入第4個(gè)物品的重量和價(jià)值469.9請(qǐng)輸入背包容積；7.圖市物品的編號(hào)和重量分■別為:1.002.002.003.0G4.00 2.0Q：12.3OPressanytocontinue搜狗拼音新入法必;|<主要代碼如下：#include<stdio.h>#defineM4structnode{floatno;//編號(hào)floatvalue;floatweight;floatwweight;//若是最后一個(gè)的用量intflag;}Node[M],temp;floatValue,curvalue=0;floatWeight,curweight=0;//按性價(jià)比排序voidsort(){inti,j;for(i=0;i<M-1;i++){for(j=i+1;j<M;j++)if((Node[i].value/(float)Node[i].weight)<Node[j].value/(float)Node[j].weight)temp=Node[i];Node[i]=Node[j];第頁(yè)共頁(yè)華北電力大學(xué)實(shí)驗(yàn)報(bào)告Node[j]=temp;))))〃可切割裝載方法voidload2(){inti;for(i=0;i<M;i++){if((Node[i].weight+curweight)<=Weight){curvalue+=Node[i].value;curweight+=Node[i].weight;Node[i].flag=1;)elseif((Node[i].weight+curweight)>Weight&&(curweight<Weight)){floatt=Weight-curweight;curvalue+=(Node[i].value)/(Node[i].weight)*t;curweight=Weight;Node[i].flag=2;Node[i].wweight=t;)else{Node[i].flag=0;)))〃進(jìn)行結(jié)果的輸出voidputout(){inti;printf("選中物品的編號(hào)和重量分別為：")；printf("\n\r");for(i=0;i<M;i++){if(Node[i].flag==1){printf("%.2f",Node[i].no);printf("");printf("%.2f",Node[i].weight);printf("\n\r");)elseif(Node[i].flag==2){printf("%.2f",Node[i].no);printf("");printf("%.2f",Node[i].wweight);printf("\n\r");)第頁(yè)共頁(yè)華北電力大學(xué)實(shí)驗(yàn)報(bào)告)printf("\n總價(jià)值為:%.2f",curvalue);)intmain(){inti;staticintp;printf("請(qǐng)輸入物品的重量和價(jià)值：\n");for(i=0;i<M;i++){printf("請(qǐng)輸入第％~個(gè)物品的重量和價(jià)值，i+1);scanf("%f%f%f",&Node[i].no,&Node[i].weight,&Node[i].value);)printf("\n請(qǐng)輸入背包容積：");scanf("%f",&Weight);sort();load2();putout();return0;)[綜合實(shí)驗(yàn)六](選做)0-1背包問(wèn)題的求解一、實(shí)驗(yàn)內(nèi)容：0-1背包問(wèn)題有多種解法，如動(dòng)態(tài)規(guī)劃方法，回溯方法，分枝限界方法等。對(duì)于同一種問(wèn)題，請(qǐng)參照教材中的算法，給出相應(yīng)的程序?qū)崿F(xiàn)。注：0/1背包問(wèn)題：給定幾種物品和一個(gè)容量為。的背包，物品》的重量是w,，其價(jià)值為匕，背包問(wèn)題是如何使選擇裝入背包內(nèi)的物品，使得裝入背包中的物品的總價(jià)值最大。其中，每種物品只有全部裝入背包或不裝入背包兩種選擇。二、所用算法的基本思想及復(fù)雜度分析：.動(dòng)態(tài)規(guī)劃法求解0/1背包問(wèn)題：1)基本思想：令v(，j)表示在前,(1?話n)個(gè)物品中能夠裝入容量為j(1?j?G的背包中的物品的最大值，則可以得到如下動(dòng)態(tài)函數(shù)：V(,,0)=V(0,j)=0v(,.)=|V(Tj)(j<w)“，/ [maxV(i-1,j),V(i-1,j-w)+v}(j>w)ii i按照下述方法來(lái)劃分階段：第一階段，只裝入前1個(gè)物品，確定在各種情況下的背包能夠得到的最大價(jià)值；第二階段，只裝入前2個(gè)物品，確定在各種情況下的背包能夠得到的最大價(jià)值；以此類推，直到第n個(gè)階段。最后，v(n，G便是在容量為。的背包中第頁(yè)共頁(yè)華北電力大學(xué)實(shí)驗(yàn)報(bào)告裝入n個(gè)物品時(shí)取得的最大價(jià)值。2)代碼:#include<iostream>#include<algorithm>usingnamespacestd;#defineN100 〃最多可能物體數(shù)structgoods〃物品結(jié)構(gòu)體(intsign;〃物品序號(hào)intw; 〃物品重量intp; 〃物品價(jià)值}a[N];boolm(goodsa,goodsb)(return(a.p/a.w)>(b.p/b.w);}intmax(inta,intb)(returna<b?b:a;intn,C,bestP=0,cp=0,cw=0;intX[N],cx[N];intKnapSack2(intn,goodsa[],intC,intx[])(intV[N][10*N];for(inti=0;i<=n;i++) 〃初始化第0歹UV[i][0]=0;for(intj=0;j<=C;j++) 〃初始化第0行V[0][j]=0;for(i=1;i<=n;i++) //計(jì)算第i行，進(jìn)行第i次迭代for(j=1;j<=C;j++)if(j<a[i-1].w)V[i][j]=V[i-1][j];elseV[i][j]=max(V[i-1][j],V[i-1][j-a[i-1].w]+a[i-1].p);j=C;//求裝入背包的物品for(i=n;i>0;i--)(if(V[i][j]>V[i-1][j]){x[i-1]=1;j=j-a[i-1].w;}elsex[i-1]=0;第頁(yè)共頁(yè)華北電力大學(xué)實(shí)驗(yàn)報(bào)告returnV[n][C]; 〃返回背包取得的最大價(jià)值)intmain()(goodsb[N];printf("物品種數(shù)n:");scanf("%d",&n);〃輸入物品種數(shù)printf("背包容量C:");scanf("%d",&C);〃輸入背包容量for(inti=0;i<n;i++) 〃輸入物品i的重量w及其價(jià)值v(printf("物品％d的重量w[%d]及其價(jià)值v[%d]:",i+1,i+1,i+1);scanf("%d%d",&a[i].w,&a[i].p);b[i]=a[i];)intsum2=KnapSack2(n,a,C,X);〃調(diào)用動(dòng)態(tài)規(guī)劃法求0/1背包問(wèn)題printf("動(dòng)態(tài)規(guī)劃法求解0/1背包問(wèn)題:\nX=[");for(i=0;i<n;i++)cout<<X[i]<<"";//輸出所求X[n]矩陣printf("]裝入總價(jià)值％d\n",sum2);for(i=0;i<n;i++)(a[i]=b[i];}//恢復(fù)2時(shí)順序)3)運(yùn)行結(jié)果：■J"DAProgramFilesWC...一口物品種數(shù)亦:6背包容量j30物品1的重量W1］及其價(jià)值］：物品2的重量及其價(jià)值“司：物品？的重量川國(guó)及其價(jià)值u［刃:物品年的重量W"】及其價(jià)值“4】：物品5的重量嘰5］及其價(jià)值45］：物品G的重量及其價(jià)值：動(dòng)態(tài)規(guī)劃法求解日門背包問(wèn)題：57S12121814209161935x=[000011)Pressangkeytoeontinuo,裝入總價(jià)值51搜狗拼音輸入法全：4)復(fù)雜度分析:動(dòng)態(tài)規(guī)劃法求解0/1背包問(wèn)題的時(shí)間復(fù)雜度為：T(n)=3nxO。第頁(yè)共頁(yè)華北電力大學(xué)實(shí)驗(yàn)報(bào)告.回溯法求解0/1背包問(wèn)題：1)基本思想：回溯法：為了避免生成那些不可能產(chǎn)生最佳解的問(wèn)題狀態(tài)，要不斷地利用限界函數(shù)(boundingfunction)來(lái)處死那些實(shí)際上不可能產(chǎn)生所需解的活結(jié)點(diǎn)，以減少問(wèn)題的計(jì)算量。這種具有限界函數(shù)的深度優(yōu)先生成法稱為回溯法。對(duì)于有n種可選物品的0/1背包問(wèn)題，其解空間由長(zhǎng)度為n的0-1向量組成,可用子集數(shù)表示。在搜索解空間樹時(shí)，只要其左兒子結(jié)點(diǎn)是一個(gè)可行結(jié)點(diǎn)，搜索就進(jìn)入左子樹。當(dāng)右子樹中有可能包含最優(yōu)解時(shí)就進(jìn)入右子樹搜索。2)代碼：#include<iostream>#include<algorithm>usingnamespacestd;#defineN100〃最多可能物體數(shù)structgoods〃物品結(jié)構(gòu)體(intsign;〃物品序號(hào)intw;〃物品重量intp;〃物品價(jià)值}a[N];boolm(goodsa,goodsb)(return(a.p/a.w)>(b.p/b.w);}intmax(inta,intb)(returna<b?b:a;}intn,C,bestP=0,cp=0,cw=0;intX[N],cx[N];intBackTrack(inti)(if(i>n-1){if(bestP<cp){for(intk=0;k<n;k++)X[k]=cx[k];//存儲(chǔ)最優(yōu)路徑

bestP=cp;}returnbestP;}if(cw+a[i].w<=C){//進(jìn)入左子樹cw=cw+a[i].w;cp=cp+a[i].p;cx[a[i].sign]=1;//裝入背包BackTrack(i+1);第頁(yè)共頁(yè)華北電力大學(xué)實(shí)驗(yàn)報(bào)告cw=cw-a[i].w;cp=cp-a[i].p;〃回溯，進(jìn)入右子樹)cx[a[i].sign]=0;//不裝入背包BackTrack(i+1);returnbestP;)intKnapSack3(intn,goodsa[],intC,intx[])(for(inti=0;i<n;i++)(x[i]=0;a[i].sign=i;)sort(a,a+n,m);//將各物品按單位重量?jī)r(jià)值降序排列BackTrack(0);returnbestP;)intmain()(goodsb[N];printf("物品種數(shù)n:");scanf("%d",&n); 〃輸入物品種數(shù)printf("背包容量C:");scanf("%d",&C); 〃輸入背包容量for(inti=0;i<n;i++)//輸入物品i的重量w及其價(jià)值v(printf("物品％d的重量w[%d]及其價(jià)值v[%d]:",i+1,i+1,i+1);scanf("%d%d",&a[i].w,&a[i].p);b[i]=a[i];)intsum3=KnapSack3(n,a,C,X);//調(diào)用回溯法求0/1背包問(wèn)題printf("回溯法求解0/1背包問(wèn)題:\nX=[");for(i=0;i<n;i++)cout<<X[i]<<"";//輸出所求X[n]矩陣printf("]裝入總價(jià)值％d\n",sum3);for(i=0;i<n;i++)(a[i]=b[i];}//恢復(fù)2網(wǎng)]順序3)運(yùn)行結(jié)果：第頁(yè)共頁(yè)華北電力大學(xué)實(shí)驗(yàn)報(bào)告nD;\ProgramFiles\?.一物品種數(shù)n：6背包容量C：3G物品1的重量川口】及其價(jià)值?？凇浚?219物品之時(shí)重裝嘰司及再價(jià)值3幻：25吻皿3的重廷川【用,交其價(jià)值?！敬颍?423呦品4的重量141H及其價(jià)值中網(wǎng)1；819料而5的重最u[5]及其儕恒。[5]：916物品G的重量川[6]及其怖值u[G]：712回溯法求解。門背包問(wèn)題：X=[001101]裝入總價(jià)值60Pressanyk?ytocontinue搜狗拼音輸入法全：4)復(fù)雜度分析：最不理想的情況下，回溯法求解0/1背包問(wèn)題的時(shí)間復(fù)雜度為：T(n)O(2n)。由于其對(duì)蠻力法進(jìn)行優(yōu)化后的算法，其復(fù)雜度一般比蠻力法要小?？臻g復(fù)雜度：有n個(gè)物品，即最多遞歸n層，存儲(chǔ)物品信息就是一個(gè)一維數(shù)組，即回溯法求解0/1背包問(wèn)題的空間復(fù)雜度為O(n)。.分支限界法求解背包問(wèn)題：1)基本思想：分支限界法類似于回溯法，也是在問(wèn)題的解空間上搜索問(wèn)題解的算法。一般情況下，分支限界法與回溯法的求解目標(biāo)不同?；厮莘ǖ那蠼饽繕?biāo)是找出解空間中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出使某一目標(biāo)函數(shù)值達(dá)到極大或極小的解，即在某種意義下的最優(yōu)解。首先，要對(duì)輸入數(shù)據(jù)進(jìn)行預(yù)處理，將各物品依其單位重量?jī)r(jià)值從大到小進(jìn)行排列。在下面描述的優(yōu)先隊(duì)列分支限界法中，節(jié)點(diǎn)的優(yōu)先級(jí)由已裝袋的物品價(jià)值加上剩下的最大單位重量?jī)r(jià)值的物品裝滿剩余容量的價(jià)值和。算法首先檢查當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒子結(jié)點(diǎn)的可行性。如果該左兒子結(jié)點(diǎn)是可行結(jié)點(diǎn)，則將它加入到子集樹和活結(jié)點(diǎn)優(yōu)先隊(duì)列中。當(dāng)前擴(kuò)展結(jié)點(diǎn)的右兒子結(jié)點(diǎn)一定是可行結(jié)點(diǎn)，僅當(dāng)右兒子結(jié)點(diǎn)滿足上界約束時(shí)才將它加入子集樹和活結(jié)點(diǎn)優(yōu)先隊(duì)列。當(dāng)擴(kuò)展到葉節(jié)點(diǎn)時(shí)為問(wèn)題的最優(yōu)值。2)代碼:#include<iostream>#include<algorithm>usingnamespacestd;#defineN100 〃最多可能物體數(shù)structgoods〃物品結(jié)構(gòu)體(intsign;〃物品序號(hào)intw; 〃物品重量intp; 〃物品價(jià)值}a[N];boolm(goodsa,goodsb)第頁(yè)共頁(yè)華北電力大學(xué)實(shí)驗(yàn)報(bào)告return(a.p/a.w)>(b.p/b.w);)intmax(inta,intb)(returna<b?b:a;)intn,C,bestP=0,cp=0,cw=0;intX[N],cx[N];structKNAPNODE//狀態(tài)結(jié)構(gòu)體(bools1[N];//當(dāng)前放入物體intk; //搜索深度intb; 〃價(jià)值上界intw; 〃物體重量intp; 〃物體價(jià)值);structHEAP //堆元素結(jié)構(gòu)體(KNAPNODE*p;//結(jié)點(diǎn)數(shù)據(jù)intb; 〃所指結(jié)點(diǎn)的上界);〃交換兩個(gè)堆元素voidswap(HEAP&a,HEAP&b)(HEAPtemp=a;a=b;b=temp;)//堆中元素上移voidmov_up(HEAPH[],inti)(booldone=false;if(i!=1){while(!done&&i!=1){if(H[i].b>H[i/2].b){swap(H[i],H[i/2]);}else{done=true;}i=i/2;}}}//堆中元素下移第頁(yè)共頁(yè)華北電力大學(xué)實(shí)驗(yàn)報(bào)告voidmov_down(HEAPH[],intn,inti)(booldone=false;if((2*i)<=n){while(!done&&((i=2*i)<=n)){if(i+1<=n&&H[i+1].b>H[i].b){i++;)if(H[i/2].b<H[i].b){swap(H[i/2],H[i]);}else{done=true;}}}}〃往堆中插入結(jié)點(diǎn)voidinsert(HEAPH[],HEAPx,int&n){n++;H[n]=x;mov_up(H,n);}//刪除堆中結(jié)點(diǎn)voiddel(HEAPH[],int&n,inti){HEAPx,y;x=H[i];y=H[n];n--;if(i<=n){H[i]=y;if(y.b>=x.b){mov_up(H,i);}else{mov_down(H,n,i);}}}//獲得堆頂元素并刪除HEAPdel_top(HEAPH[],int&n){HEAPx=H[1];del(H,n,1);returnx;第頁(yè)共頁(yè)華北電力大學(xué)實(shí)驗(yàn)報(bào)告〃計(jì)算分支節(jié)點(diǎn)的上界voidbound(KNAPNODE*node,intM,goodsa[],intn)(inti=node->k;floatw=node->w;floatp=node->p;if(node->w>M){//物體重量超過(guò)背包載重量node->b=0; //上界置為0}else{while((w+a[i].w<=M)&&(i<n)){w+=a[i].w; //計(jì)算背包已裝入載重p+=a[i++].p;// 計(jì)算背包已裝入價(jià)值}if(i<n){node->b=p+(M-w)*a[i].p/a[i].w;}else{node->b=p;}}}//用分支限界法實(shí)現(xiàn)0/1背包問(wèn)題intKnapSack4(intn,goodsa[],intC,intX[]){inti,k=0; //堆中元素個(gè)數(shù)的計(jì)數(shù)器初始化為0intv;KNAPNODE*xnode,*ynode,*znode;HEAPx,y,z,*heap;heap=newHEAP[n*n]; //分配堆的存儲(chǔ)空間for(i=0;i<n;i++){a[i].sign=i; 〃記錄物體的初始編號(hào)}sort(a,a+n,m); //對(duì)物體按照價(jià)值重量比排序xnode=newKNAPNODE; //建立父親結(jié)點(diǎn)for(i=0;i<n;i++){ /