【文章內(nèi)容簡介】 loat p。 //物品效益 float w。 //物品重量 float X。 //物品該放的數(shù)量 int flag。 //物品編號}。//物品信息結(jié)構(gòu)體void Insertionsort(goodinfo goods[],int n){ int j,i。 for(j=2。j=n。j++) { goods[0]=goods[j]。 i=j1。 while (goods[0].pgoods[i].p) { goods[i+1]=goods[i]。 i。 } goods[i+1]=goods[0]。 }}//按物品效益，重量比值做升序排列void bag(goodinfo goods[],float M,int n){ float cu。 int i,j。 for(i=1。i=n。i++) goods[i].X=0。 cu=M。 //背包剩余容量 for(i=1。in。i++) { if(goods[i].wcu)//當(dāng)該物品重量大與剩余容量跳出 break。 goods[i].X=1。 cu=cugoods[i].w。//確定背包新的剩余容量 } if(i=n) goods[i].X=cu/goods[i].w。//該物品所要放的量for(j=2。j=n。j++) { goods[0]=goods[j]。 i=j1。 while (goods[0].flaggoods[i].flag) { goods[i+1]=goods[i]。 i。 } goods[i+1]=goods[0]。 }cout最優(yōu)解為:endl。 for(i=1。i=n。i++) { cout第i件物品要放:。 coutgoods[i].Xendl。 }}void main(){ cout|運用貪心法解背包問題|endl。 cout||endl。 int j。 int n。 float M。 goodinfo *goods。//定義一個指針 while(j) { cout請輸入物品的總數(shù)量：。 cinn。 goods=new struct goodinfo [n+1]。// cout請輸入背包的最大容量：。 cinM。 coutendl。 int i。 for(i=1。i=n。i++) { goods[i].flag=i。 cout請輸入第i件物品的重量:。 cingoods[i].w。 cout請輸入第i件物品的效益:。 cingoods[i].p。 goods[i].p=goods[i].p/goods[i].w。//得出物品的效益，重量比 coutendl。 } Insertionsort(goods,n)。 bag(goods,M,n)。 coutpress 1 to run agianendl。 coutpress 0 to exitendl。 cinj。 }}2. Prim算法include include include define INFINITY INT_MAX define MAX_VERTEX_NUM 20 typedef int VRType。typedef int InfoType。typedef char VerTexType。typedef struct ArcCell{ VRType adj。 InfoType *info。 }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]。typedef struct{ VerTexType vexs[MAX_VERTEX_NUM]。 AdjMatrix arcs。 int vexnum, arum。 }MGraph。typedef struct{ VerTexType adjvex。 VRType lowcost。}closedge[MAX_VERTEX_NUM]。void CreateGraph(MGraph amp。G)。void MiniSpanTree_PRIM(MGraph G, VerTexType u)。int LocateVex(MGraph G, VerTexType u)。int minimum(closedge close)。void main( void ){ int i, j。 MGraph G。 CreateGraph(G)。 for(i = 0。 i 。 i++) { for(j = 0。 j 。 j++) { cout[i][j].adj。 cout 。 } coutendl。 } MiniSpanTree_PRIM(G, 39。a39。)。}void CreateGraph(MGraph amp。G){ int weigh。 int i, j = 0, k = 0。 char hand, tide。 coutinput the number for vexnum and arum:。 cin。 for(i = 0。 i 。 i++) { for(j = 0。 j 。 j++) [i][j].adj = 88。 } coutendl。 coutinputchar for vexs:。 for(i=0。 i 。 i++) cin[i]。 coutendl。 coutinputarc(char,char,weigh):endl。 j = 0。 k = 0。 for(i=0。 i 。 i++) { couti:。 cinhand。 cintide。 cinweigh。 while (hand != [j]) j++。 while (tide != [k]) k++。 [j][k].adj = weigh。 [k][j].adj = weigh。 j = 0。 k = 0。 coutendl。 }}void MiniSpanTree_PRIM(MGraph G,VerTexType u){ int i, j, k = 0。 closedge close。 k = LocateVex ( G, u )。 for ( j = 0。 j 。 j++ ) { if (j != k) { close[j].adjvex = [k]。 close[j].lowcost = [k][j].adj。 } } close[j].lowcost = 88。 close[j].adjvex = 39。\039。 close[k].lowcost = 0。 close[k].adjvex = u。 for (i = 1。 i 。 i++) { k = minimum(close)。 coutclose[k].adjvex。 cout。 cout[k] 。 coutclose[k].lowcostendl。 close[k].lowcost = 0。 for (j=0。 j。 j++) { if ([k][j].adj close[j].lowcost) { close[j].adjvex = [k]。 close[j].lowcost = [k][j].adj。 } } }}int LocateVex(MGraph G, VerTexType u){ int k = 0。 while([k++] == u) return k1。 return 0。}int minimum(closedge close){ int j1=0, client = 88, j2。 while(close[j1].adjvex != 39。\039。) { if (client close[j1].lowcost amp。amp。 close[j1].lowcost != 0) { client = close[j1].lowcost。 j2 = j1。 } j1++。 } return j2。}1. 背包問題貪心算法2. Prim算法實驗三 動態(tài)規(guī)劃1. 理解最優(yōu)子結(jié)構(gòu)的問題。有一類問題的活動過程可以分成若干個階段，而且在任一階段后的行為依賴于該階段的狀態(tài)，與該階段之前的過程如何達到這種狀態(tài)的方式無關(guān)。這類問題的解決是多階