【正文】 losedge[MAX_VERTEX_NUM]。 int vexnum, arum。 InfoType *info。 }}2. Prim算法include include include define INFINITY INT_MAX define MAX_VERTEX_NUM 20 typedef int VRType。 bag(goods,M,n)。 cingoods[i].p。i++) { goods[i].flag=i。 coutendl。 cinn。 int n。 coutgoods[i].Xendl。 }cout最優(yōu)解為:endl。 i=j1。//確定背包新的剩余容量 } if(i=n) goods[i].X=cu/goods[i].w。in。i=n。 } goods[i+1]=goods[0]。j++) { goods[0]=goods[j]。 //物品編號}。 }1. 背包問題貪心算法include struct goodinfo{ float p。 ModifyCandidateSet(…)； //根據新紅點v調整候選輕邊集 //求圖G的以r為根的MST，結果放在T=(U，TE)中3. 將統計數與復雜性函數所計算的比較次數比較，用表格列出比較結果，給出文字分析。procedure GREEDY(A，n) /*貪心法一般控制流程*/ //A(1：n)包含n個輸入// solutions←φ //將解向量solution初始化為空／ for i←1 to n do x←SELECT(A) if FEASIBLE(solution，x) then solutions←UNION(solution，x) endif repeat return(solution)end GREEDY4. 實現典型的貪心算法的編程與上機實驗，驗證算法的時間復雜性函數。作出貪心決策的依據稱為貪心準則（greedy criterion）。那些使目標函數取極值(極大或極小)的可行解，稱為最優(yōu)解。 ()。 kuaisu px(a1,n)。 srand(time(0))。}。i++) coutsetw(4)b[i].key。 output()。amp。amp。 i=s。 quicksort(i+1,t)。i++) b[i]=a[i]。 }。 }2. 快速排序includeincludeincludeincludedefine MAXI 10typedef int KeyType。 (j,k,n,b)。 } guibing gx(a)。 for(i=0。 void main() { coutguibingfa1運行結果:\n。 k++。 j++。 } else { r2[k]=r[j]。amp。 int i,j,k。 b[i]=temp。jn。 for(i=m。in。class guibing{public: guibing(sqlist b) { for(int i=0。struct rec{ KeyType key。 QuickSort(j+1,q)。// int p,q。4. 用表格列出比較結果。 endifend DanC3．實現典型的分治算法的編程與上機實驗，驗證算法的時間復雜性函數。n if Small(p,q) then return G(p,q)。 integer m,p,q。算法設計與分析實驗報告 指導老師：沙莎學 院：信息科學與工程學院班 級：計科0508姓 名：戚婕學 號：10完成日期：2007年12月目 錄實驗一 分治法 ………………………………………………………………………… 2 實驗要求 ……………………………………………………………………… 2 實驗內容 ……………………………………………………………………… 2 核心算法 ……………………………………………………………………… 2 程序代碼 ……………………………………………………………………… 4 實驗結果 ……………………………………………………………………… 8實驗二 貪心法 ……………………………………………………………………… 10 實驗要求 …………………………………………………………………… 10 實驗內容 …………………………………………………………………… 10 核心算法 …………………………………………………………………… 10 程序代碼 …………………………………………………………………… 12 實驗結果 …………………………………………………………………… 18實驗三 動態(tài)規(guī)劃 ………………………………………………………………… 20 實驗要求 …………………………………………………………………… 20 實驗內容 …………………………………………………………………… 20 核心算法 …………………………………………………………………… 20 程序代碼 …………………………………………………………………… 21 實驗結果 …………………………………………………………………… 24實驗四 深度優(yōu)先搜索 …………………………………………………………… 26 實驗要求 …………………………………………………………………… 26 實驗內容 …………………………………………………………………… 26 核心算法 …………………………………………………………………… 26 程序代碼 …………………………………………………………………… 27 實驗結果 …………………………………………………………………… 28實驗五 回溯法 ……………………………………………………………………… 30 實驗要求 …………………………………………………………………… 30 實驗內容 …………………………………………………………………… 30 核心算法 …………………………………………………………………… 30 程序代碼 …………………………………………………………………… 31 實驗結果 …………………………………………………………………… 33實驗一 分治法1. 了解用分治法求解的問題：當要求解一個輸入規(guī)模為n，且n的取值相當大的問題時，如果問題可以分成k個不同子集合，得到k個不同的可獨立求解的子問題，其中1k≤n，而且子問題與原問題性質相同，原問題的解可由這些子問題的解合并得出。DanC(p,q) global n，A[1:n]。q163。mq return Combine(DanC(p,m),DanC(m+1,q))。3. 與復雜性函數所計算的比較次數比較。 , A[q]按不降次序排列， 并假定A[n+1]是一個確定的、且大于 A[1:n]中所有的數。 // 劃分后j成為劃分元素的位置 QuickSort(p,j1)。typedef int ElemType。typedef rec sqlist[M]。 } void output(sqlist r,int n) { for(int i=0。 } void xuanze(sqlist b,int m,int n) { int i,j,k。 for(j=i。 b[k]=b[i]。 output(r,M)。imamp。 i++。 } while(jh) { r2[k]=r[j]。 i++。 }。 srand(time(0))。b[i].key=0。 cout數組排序過程演示:\n。 ()。 ElemType data。in。 quicksort(s,i1)。 rec p。 while(ij) { while(ijamp。 while(ijamp。 } b[i]=p。in。 int n。 int i,n=MAXI,low=0,high=9。i++) a1[i].key=rand()%80。 cout排序后數組:\n?？?