回溯算法報(bào)告

實(shí)驗(yàn)四回溯算法的應(yīng)用一、實(shí)驗(yàn)?zāi)康囊?、?shí)驗(yàn)?zāi)康?．掌握回溯算法的基本思想、技巧和效率分析方法。2．熟練掌握用回溯算法求解問題的基本步驟，非遞歸算法框架和遞歸算法框架。3．學(xué)會(huì)利用回溯算法解決實(shí)際問題。二、算法問題要求任意給出從1到N的N個(gè)連續(xù)的自然數(shù)，求出這N個(gè)自然數(shù)的各種全排列。如N=3時(shí)，共有以下6種排列方式：123,132,213,231,312,321。注意：數(shù)字不能重復(fù)，N由鍵盤輸入。三、算法設(shè)計(jì)有N件物品和一個(gè)容量為V的背包。第i件物品的體積是v[i],價(jià)值是w[i]。求解將哪些物品裝入背包可使這些物品的費(fèi)用總和不超過背包容量,且價(jià)值總和最大。每個(gè)數(shù)的取法都有N個(gè)方向（1——N）,當(dāng)取夠N個(gè)數(shù)時(shí)，輸出一個(gè)排列，然后退后一步,取前一個(gè)數(shù)的下一個(gè)方向（即前一個(gè)數(shù)+1）,并且要保證所有數(shù)字不能重復(fù)。當(dāng)前數(shù)字的所有方向都取完時(shí),繼續(xù)退一步,一直重復(fù)到第一個(gè)數(shù)為止。、運(yùn)行結(jié)果#include<stdio.h>voidEnumList(char*,int,int);intmain(){intiNum,i;charszList[512];printf("輸入全排的數(shù)字(1~N,N<=9):\n");scanf("%d",&iNum);for(i=0;i<iNum;i++)szList[i]=i+49;szList[i]='\0';EnumList(szList,0,i);return0;};voidEnumList(char*CcList,intiBegin,intiEnd){inti;chart;if(iBegin<iEnd){EnumList(CcList,iBegin+1,iEnd);for(i=iBegin+1;i<iEnd;i++){t=CcList[iBegin];CcList[iBegin]=CcList[i];CcList[i]=t;EnumList(CcList,iBegin+1,iEnd);t=CcList[iBegin];CcList[iBegin]=CcList[i];CcList[i]=t;};}elseprintf("%s\n",CcList);};六、總結(jié)這次實(shí)驗(yàn)的內(nèi)容都很有代表性，通過上機(jī)操作實(shí)踐與對問題的思考，讓我更深層地領(lǐng)悟到了回溯算法的思想。回溯算法的基本思路并不難理解，簡單來說就是：從一條路往前走，能進(jìn)則進(jìn)，不能進(jìn)則退回來