【正文】 i++。 coutendl。 for(i=0。 ()。3. 一般方法1）根據(jù)題意，選取一種量度標準。1. 背包問題的貪心算法 procedure KNAPSACK(P，W，M，X，n) //P(1：n)和W(1；n)分別含有按 P(i)/W(i)≥P(i+1)/W(i+1)排序的n件物品的效益值 和重量。 (u，v)=SelectLiShtEdge(…)；//選取輕邊(u，v)； T←T∪{(u，v)}；//擴充T，即(u，v)涂紅加入TE，藍點v并人紅點集U //物品效益 float w。 i=j1。i++) goods[i].X=0。//該物品所要放的量for(j=2。 for(i=1。 float M。 int i。 goods[i].p=goods[i].p/goods[i].w。typedef int InfoType。 }MGraph。int minimum(closedge close)。 j++) { cout[i][j].adj。 int i, j = 0, k = 0。 j++) [i][j].adj = 88。 j = 0。 while (hand != [j]) j++。 closedge close。\039。 cout[k] 。 while([k++] == u) return k1。 j2 = j1。最優(yōu)子結(jié)構(gòu)性質(zhì)：原問題的最優(yōu)解包含了其子問題的最優(yōu)解。步驟13是動態(tài)規(guī)劃算法的基本步驟。 P(1：k)是最小成本路徑。 //指向第一條依附該頂點的弧的指針}VNode, AdjList[MAX_VERTEX_NUM]。 //圖的頂點數(shù) if(a 0) return printf(ERROR)。 m++) { i = 1。 pvalue = v。 //新開辟結(jié)點 } } return v。//第i個結(jié)點的鄰接結(jié)點信息 p = pnextarc。 for(j = n 1。 value = pvalue。 i++) //找出最小代價路徑上的結(jié)點 path[i] = d[path[i 1]]。 g = (ALGraph)malloc(sizeof(ALGraph))。 scanf(%d, amp。}多段圖問題實驗四 深度優(yōu)先搜索1． 理解深度優(yōu)先搜索策略：深度優(yōu)先搜索策略是盡可能“深”地搜索圖。2． 修改算法使之可以找出圖的所有樹。 color[u]←Gray。 //標記樹并記錄其個數(shù)void DFS(int i){ int k。B39。 cout請輸入總頂點數(shù)：\n。j++) { A[i][j]=0。 cinj。i=n。 } else { cout該圖中共有l(wèi)oop個環(huán)!endl。如果肯定不包含，則跳過對以該結(jié)點為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點回溯。 while(i k) { if((X[i] == X[k])||(abs(X[i] X[k]) == abs(i k))) //兩個皇后不在同行/列/對角線 return false。amp。 //下一列的皇后所在列位置置0 } } else {//已判斷完n列，均未能滿足條件 X[k] = 0。 scanf(%d, amp。i)。 Nqueens(n, X)。 printf(|THE N QUEENS PROBLEM|\n)。i++) //輸出各行皇后的列位置 printf(%d , X[i])。 X[1] = 0。2. 用圖形輸出中間過程。 Si 是 xi 的定義域且Si 是有窮集，稱E中滿足D 的全部約束條件的所有n元組為問題P的一個解。amp。i++) { if(color[i]==39。k=m。 for(i=1。) DFS(k)。k=n。includedefine MAX 50 //能夠處理的最多頂點數(shù) char color[MAX]。 for 每個頂點u∈G do color[u]← White。如果還存在未被發(fā)現(xiàn)的頂點，則選擇其中一個作為源結(jié)點并重復(fù)以上過程，整個進程反復(fù)進行直到所有結(jié)點都被發(fā)現(xiàn)為止。 printf(多段圖的鄰接表為:\n)。 printf(請輸入多段圖邊的數(shù)目:)。 w = k。 //決策階段，各結(jié)點到終點最小代價路徑上前方頂點的編號 } path[1] = 1。 //初始化路徑最小代價 r = padjvex。 int path[100]。 i Gvexnum。 else { //若當(dāng)前結(jié)點有后繼節(jié)點則后移 for(q = Gvertices[i].firstArc。h,amp。 m++) { Gvertices[m].data = m。int build_adList(ALGraph G,int n,int a){ //建立鄰接表 int v, m, i, t, h。 //該結(jié)點與鄰接結(jié)點間的代價 struct ArcNode *nextarc。3. 要求用文件裝入5個多段圖數(shù)據(jù)，編寫從文件到鄰接表的函數(shù)。每一點最優(yōu)都是上一點最優(yōu)加上這段長度。有一類問題的活動過程可以分成若干個階段，而且在任一階段后的行為依賴于該階段的狀態(tài)，與該階段之前的過程如何達到這種狀態(tài)的方式無關(guān)。\039。 j。 i 。 j++ ) { if (j != k) { close[j].adjvex = [k]。 j = 0。 i++) { couti:。 i 。 for(i = 0。a39。 for(i = 0。void CreateGraph(MGraph amp。 }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]。 coutpress 1 to run agianendl。 cout請輸入第i件物品的重量:。 goods=new struct goodinfo [n+1]。 }}void main(){ cout|運用貪心法解背包問題|endl。 while (goods[0].flaggoods[i].flag) { goods[i+1]=goods[i]。i++) { if(goods[i].wcu)//當(dāng)該物品重量大與剩余容量跳出 break。 }}//按物品效益，重量比值做升序排列void bag(goodinfo goods[],float M,int n){ float cu。//物品信息結(jié)構(gòu)體void Insertionsort(goodinfo goods[],int n){ int j,i。 }1. 編程實現(xiàn)背包問題貪心算法和最小生成樹prim算法。2. 貪心法求優(yōu)化問題算法思想：在貪心算法中采用逐步構(gòu)造最優(yōu)解的方法。 cout數(shù)組排序過程演示:\n。void main(){ cout:\n。 return i。b[j].key=)j。 } else return。typedef rec sqlist[MAXI]。 cout排序后數(shù)組:\n。iM。 } output(r2,M)。 j++。 k=i=l。j++) if(b[k].keyb[j].key) k=j。i++) coutsetw(4)r[i].key。 ElemType data。 global n, A[1:n]。1. 編程實現(xiàn)歸并排序算法和快速排序算法，程序中加入比較次數(shù)的計數(shù)功能，輸出排序結(jié)果和比較次數(shù)。 // 1163。2. 掌握分治法的一般控制流程。 // p163。1. 歸并排序算法procedure MERGESORT(low，high) //A(low；high)是一個全程數(shù)組，它含有highlow+1≥0個待排序的元素// integer low，high； if lowhigh； then mid← ， //求這個集合的分割點// call MERGESORT(low，mid) //將一個子集合排序// call MERGESORT(mid+1，high) //將另一個子集合排序 call MERGE(low，mid，high) //歸并兩個已排序的子集合// endif end MERGESORT歸并兩個已排序的集合 procedure MERGE(lo