算法設(shè)計與分析課程設(shè)計報告-文庫吧資料
2024-08-18 11:01本頁面
【正文】 if(cw+x[i]*w[i]=c) { cw+=w[i]*x[i]。j=1。i++) bestx[i]=x[i]。 for(i=0。//物品的價值，物品的重量，x[i]暫存物品的選中情況,物品的選中情況void Backtrack(int i,int cp,int cw){ //cw當(dāng)前包內(nèi)物品重量，cp當(dāng)前包內(nèi)物品價值 int j。 }}2．0/1背包問題includeint n,c,bestp。 scanf(%d,amp。 bag(goods,M,n)。 printf(\n)。goods[i].p )。 printf(請輸入第%d個物品的價值：,i)。 scanf(%f,amp。i++) { goods[i].flag =i。 for (int i=1。M)。 printf(請輸入背包的最大容量: )。n)。 while (j) { printf(請輸入物品的總數(shù)量: )。 float M。 }}void main(){ printf(運(yùn)用貪心算法求解普通背包問題\n)。i++) { printf(第%d件物品要放: %f,goods[i].flag ,goods[i].x )。 for(i=1。 } goods[i+1]=goods[0]。 while (goods[0].flag goods[i].flag ) { goods[i+1]=goods[i]。j++) { goods[0]=goods[j]。//該物品所要放的量 } //按物品編號做降序排列 for(j=2。 cu=cugoods[i].w 。i++) { if(goods[i].wcu) break。 for(i=1。i++) goods[i].x=0。 for(i=1。 } }//按物品效益重量比值做降序排列void bag(goodinfo goods[],float M,int n){ float cu。 i。 i=j1。j=n。void Insertionsort(goodinfo goods[],int n){ int i,j。//物品該放數(shù)量 int flag。//物品價值 float w。 （3）使用memset(Matrix,0,sizeof(Matrix))將Matrix[]數(shù)組清零。算法設(shè)計：（1）ChessBoard函數(shù)實現(xiàn)了遞歸的將棋盤劃分為子棋盤，并將棋盤進(jìn)行覆蓋。算法設(shè)計：，背包容量為C，分別用p[i]和w[i]存儲第i種物品的價值和重量，用x[i]標(biāo)記第i種物品是否裝入背包，用bestx[i]存儲第i種物品的最優(yōu)裝載方案；b. 用遞歸函數(shù)Backtrack (i,cp,cw)來實現(xiàn)回溯法搜索子集樹（形式參數(shù)i表示遞歸深度，n用來控制遞歸深度，形式參數(shù)cp和cw表示當(dāng)前總價值和總重量，bestp表示當(dāng)前最優(yōu)總價值）：① 若i n，則算法搜索到一個葉結(jié)點，判斷當(dāng)前總價值是否最優(yōu)：1 若cpbestp，更新當(dāng)前最優(yōu)總價值為當(dāng)前總價值（即bestp=cp），更新裝載方案（即bestx[i]=x[i]( 1≤i≤n)）；② 采用for循環(huán)對物品i裝與不裝兩種情況進(jìn)行討論（0≤j≤1）：1 x[i]=j；2 若總重量不大于背包容量（即cw+x[i]*w[i]=c），則更新當(dāng)前總價 br= 值和總重量（即cw+=w[i]*x[i],cp+=p[i]*x[i]）, 對物品i+1調(diào)用遞
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1