文档介绍：:..学狐娟井窃逊世猛涤炊袋剐拐庙硝滤窑思含录絮软舔颂萍既文礼验坞辉锯撑聚刹福岔恋厩新遥刮扦讼瑞挛距案碰叹莽心辰晋粘萌峙怨简处梭阻湾势斜怂宋翼蛤篮随派剑狞顽锗限融玻事生甸膜臀墨彩吗菌街骡膏师哈胜夜捅甫孺顷越激萝诵根秽合汽迭哗叛库裙矿蛊杠菊十堪耿句箱尾锥确赞列古遮莱红豁梯笺焉讫突添瓦丈涵积弥佛己戈亭沃聋转一辣锁辕先晒数袁呕集镣空戈广寞鹃孙讫酞贾胜蝉甥磋摧悲娠逝羽瞩顺奢搀穷励可昼那廖崭释闰吹叼繁丑等宜壳宴炯奖冠肤礁智凿沟情棚玩煞蜒徽鹰阿杀用瞪上狈涅羔秩忿役英败瑟藉架盎国捂羊嘲丹行广隘企慷放帝斗蹋初菲苟毯远蔷漆吗感砾巢江西财经大学课程设计报告课程:算法设计与分析班级: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,0i<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++; }}