背包問題的貪心算法(已修改)
2025-04-06 07:26 本頁面
【正文】 貪心方法：總是對當前的問題作最好的選擇，也就是局部尋優(yōu)。最后得到整體最優(yōu)。應用：1：該問題可以通過“局部尋優(yōu)”逐步過渡到“整體最優(yōu)”。貪心選擇性質(zhì)與“動態(tài)規(guī)劃”的主要差別。2：最優(yōu)子結(jié)構(gòu)性質(zhì)：某個問題的整體最優(yōu)解包含了“子”問題的最優(yōu)解。代碼如下：include struct goodinfo{float 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)//當該物品重量大與剩余容量跳出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|power by zhanjiantao(028054115)|endl。cout||endl。int j。int n。float M。goodinfo *goods。//定義一個指針while(j){cout請輸入物品的總數(shù)量：。cinn。goods=new struct goodinfo [n+1]
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號-1