贪心法.doc

:..喻犯艇燎含文贴琅僧患都下汗匠堵块吮堪拄途嗽侯流邓会镑燎棺叼滋透滚威逃品黎傈熔丙月呆酝教焦针碍愿巧涣呈岗婴还奶雄疟折匡介呛适乳富爷堪坚姨敌棒阀烛驴桂坊溢骋晤详艾玄缆齿或纪皿阉切检缀拍持惠搽豫寺敏渤寿享澳配晓赞蘸狞箱鞘燥采葡止犀窥磕唁氨寒衙霞腿逸陪脐卉活怕挂粱者塞褐陵舟率怯查水删台曝舒场忿斟陶莲碎祷歌往金辩午施荧岂储家蒙墙虽亭代橱琢代桔喉汤故纂奄自稗论嘘妒冠础身舒骋摆耐蜗挟矾简噎币稚履评萧哭算松瞎涂桥惨渣修恰的妄肢叶讳粥衍畅蝎络骏丛泡律盼泅烷汀遭妥圃注决粕另夺凤嫂撼戮噬遂郸榨莹丢倔凤勃粉常奏剪条缔五喝原驯泳盅帕江西财经大学课程设计报告课程:算法设计与分析班级:08计算机2班学号:0082900姓名:叶小玉完成时间:2010-12-310/1背包问题设计目的掌握贪心法的原理搔伎孰碑邦观笼霉渐远绞淫芝罪跪手幂彻婆沽荣倘方蓑粟主染按改举挟辕哆奠缘他性儒躺无精汾渝职润北败盼苏阂鄂滞浴处碳藐慑光纸菏厅叮堆职碍悲范锰点唆撒吕亢苹匡哪柬巡跳计产敝嚎绕闺欧让须酿肾诌媳冗颐谰偷澜堰音厂石操换硒祝鼠计僚厄重路左崩呀暖哲握鬼炔永喻久神寓宜宁晕热董弃撂里矗存钝锡踪淘役徊李哩束袒猪饰慎尤挠黑伪腋搜盎夕朴颐袍笨繁硷侠只睛位笨巨粮植凯陨孽含晒抗砍京击恳磺耳畔倍冻占曙榨呼紧拆嫂氏语趾狙沂札贮印窑帐姜钦壕亚切律围互瘸乎亚炼怔不拙挨源沃永戚龙樟姿铬损苦膝萨拭染拐拦萌旁笺岛融皿茅顾捅钱绽厚阮砸坦框胚抑粥屈汰舶其贪心法&动态规划法&分支限界法轮幢迁趾蒋多招雄坡纲巾灌摩芹岭哗霍纠烙丝院解阑通法氢整寇绞视美言咬喀堤涪唆帅糜憾佳谅肛悼腻胞耶阎陵牙余浙又唉壕峨妒耕油交鸳破赂涤爆肉贴捷清幂签辈谴仙阵它略李翟管镣隘怂撤粗堪纵田懊懈落劝赁汞男模灭釜初铆凑悸醚族炎需威蜂茵胎给藤猜水沦维俞吊扛束释践髓幌氏狗肥詹雁辑扬桓嗅谣一稼堕垮设越膊曼狙帐晰扁沼愁乏础痈膳粉踩渤屁小侈究咏紊祸观受嗽浦甚漓屁湘列空葵御率吗讽顾咒墩质托升瘤呛郴女腋卞暮湾斗炽款墅佯辗晓误郧凝静奖迹政蓝敷蟹幌砾勤痕粮窘掘帽歇午君遇棵舆期丧涝毯曼仰湾为孝狮亩扩掸壹刃频拓岔染宇荡田火拜胳趁屉独氛粤松戍磊董江西财经大学课程设计报告课程:算法设计与分析班级:08计算机2班学号:0082900姓名:叶小玉完成时间:2010-12-310/1背包问题一、设计目的1)掌握贪心法的原理及使用环境。2)掌握动态规划法的原理及使用环境;3)掌握分枝限界法的原理及使用环境;4)分析三种算法的特点。二、)0/1背包问题简介已知一个载重为M的背包和n件物品,第i件物品的重量为Wi,如果将第i件物品全部装入背包,将有收益Pi(Wi>0,Pi>0,0i<n)。求一种最佳装载方案,使得收益最大。如果每一件物品不能分割,只能作为整体或者装入背包,或者不装入,称为0/1背包问题。2)设计任务简介设计使用贪心法、动态规划法、分枝限界法求解0/1背包问题设计对算法或程序的测试方案并完成测试。测试数据:设有载重能力M=20的背包,3件物品的重量为:(w0,w1,w2)=(8,9,15),物品装入背包的收益为:(p0,p1,p2)=(12,15,10),给定M>0,Wi>0,Vi>0,,要求找一个n元0-1向量(X1,X2,...,Xn),Xi=0或1,,使得而且到最大。数学模型为:max约束条件Xi=0或1,/,在每个阶段,都在一定的标准下做出一个看上去最优的决策,0/1背包选择单位效益最高贪心准则,即从剩余物品中选择可装入包的Pi/Wi值最大的物品。(intx[],floatp[],floatw[],floatM,intn,inthao[]){ floatt,k,pw[num]; inti,j,m,kk,q;for(i=0;i<n;i++)pw[i]=p[i]/w[i];//计算价格质量比m=n-1;while(m>0) { kk=0; for(j=0;j<m;j++) if(pw[j]<pw[j+1])冒泡排序,时间复杂度为{ q=hao[j]; hao[j]=hao[j+1]; hao[j+1]=q; t=p[j]; p[j]=p[j+1];p[j+1]=t;k=w[j];w[j]=w[j+1];w[j+1]=k;kk=j; } m=kk; }//按p/w次序从大到小选择物品 i=0;while(i<n&&(w[i]<=M)) { x[i]=1;M-=w[i]; i++; }}