算法分析与设计贪心算法求解背包问题

用贪心算法求解背包问题D软件101 薛思雨 511020825一、贪心算法介绍顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。贪心算法求解的问题一般具有两个重要性质：贪心选择性质和最优子结构性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择来到达。这是贪心算法可行的第一个根本要素，也是贪心算法与动态规划算法的主要区别。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。二、贪心法的根本思路从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当到达某算法中的某一步不能再继续前进时，。该算法存在问题：1. 不能保证求得的最后解是最正确的；2. 不能用来求最大或最小解问题；3. 只能求满足某些约束条件的可行解的范围。三、关于贪心算法在背包问题中的应用的探讨问题描述：0-1背包问题：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包(1)或不装入背包(0)。不能将物品i装入背包屡次，也不能只装入局部的物品i。背包问题：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一局部，而不一定要全部装入背包，1in。贪心算法解决背包问题有几种策略：(i) 一种贪婪准那么为：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规那么，价值最大的物品首先被装入假设有足够容量，然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑n=2, w=100,10,10, p =20,15,15, c = 105。当利用价值贪婪准那么时，获得的解为x= 1 , 0 , 0 ，这种方案的总价值为2 0。而最优解为 0 , 1 , 1 ，其总价值为3 0。(ii) 另一种方案是重量贪婪准那么是：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规那么对于前面的例子能产生最优解，但在一般情况下那么不一定能得到最优解。考虑n= 2 ,w=10,20, p=5,100, c= 2 5。当利用重量贪婪策略时，获得的解为x =1,0, 比最优解 0 , 1 要差。(iii) 还有一种贪婪准那么，就是我们教材上提到的，认为，每一项计算yi=vi/si,即该项值和大小的比，再按比值的降序来排序，从第一项开始装背包，然后是第二项，依次类推，尽可能的多放，直到装满背包。有的参考资料也称为价值密度pi/wi贪婪算法。这种策略也不能保证得到最优解。利用此策略试解n= 3 ,w=20,15,15, p=40,25,25, c=30 时的最优解。虽然按pi /wi 非递增减的次序装入物品不能保证得到最优解，但它是一个直觉上近似的解。而且这是解决普通背包问题的最优解，因为在选择物品i装入背包时，可以选择物品i的一局部，而不一定要全部装入背包，1in。贪心算法解决背包问题的算法实现：#include iostream using namespace std; struct goodinfo float p; /物品效益 float w; /物品重量 float X; /物品该放的数量 int flag; /物品编号 ;/物品信息结构体 void Insertionsort(goodinfo goods,int n) int j,i; for(j=2;jgoodsi.p) goodsi+1=goodsi; i-; goodsi+1=goods0; /按物品效益，重量比值做升序排列 void bag(goodinfo goods,float M,int n) float cu; int i,j; for(i=1;i=n;i+) goodsi.X=0; cu=M; /背包剩余容量 for(i=1;icu)/当该物品重量大与剩余容量跳出 break; goodsi.X=1; cu=cu-goodsi.w;/确定背包新的剩余容量 if(i=n) goodsi.X=cu/goodsi.w;/该物品所要放的量 /按物品编号做降序排列 for(j=2;j=n;j+) goods0=goodsj; i=j-1; while (goods0.flaggoodsi.flag) goodsi+1=goodsi; i-; goodsi+1=goods0; cout最优解为:endl; for(i=1;i=n;i+) cout第i件物品要放:; coutgoodsi.Xendl; int main(void) cout|-运用贪心法解背包问题-|endl; cout|-|endl; int i,j,n; float M; goodinfo *goods; /定义一个指针 coutpress to run the programendl; coutpress to exitj; while(j) coutn; goods=new struct goodinfo n+1; coutM; coutendl; for(i=1;i=n;i+) goodsi.flag=i; cout请输入第igoodsi.w; cout请输入第igoodsi.p; goodsi.p=goodsi.p/goodsi.w; /得出物品的效益，重量比 coutendl; Insertionsort(goods,n); bag(goods,M,n); coutpress to run agianendl; coutpress to exitj; system(pause); return 0; 四、结果分析：对于0-1背包问题，贪心算法之所以不能得到最优解是因为在这种情况下，它无法保证最后能将背包装满，局部闲置的背包空间，使每公斤背包的价值降低了。以上算法的时间复杂度和空间复杂度为O(n*n)，其中时间复杂度根本已经不能再优化了，但空间复杂度可以优化到O(n)。下面是赠送的两篇散文欣赏，可以仔细阅读，不需要的朋友可以下载后编辑删除！谢谢！脚下的时光不知走过多少地方，不知看过多少风景，不知听说过多少轶事；不知经历过多少岁月，不知邂逅过多少良人，不知变换过多少心情；不知理想的未知是否在前路等待题记：蒲公英悠悠岁月，时间苍苍！(文章阅读网： )在这繁花似锦的青葱岁月里，我们不断的接受新鲜的美好事物，不断的享受科技开展所带来的高品质生活；我们总是随大流的，去跟风一些前卫潮流的思想；然而，很少有人去整理那些过往的断壁残垣！我走过很多地方，但是同样的，我也有更多的地方没去过！我渴望走遍地球上每一寸土地，我期许世界上每一个地方的人都善良！从踏入社会的那一刻起，我就觉得人应该是自由的；应该去做自己喜欢的事，看自己喜欢的风景，爱自己喜欢的人；一切都那么单纯，完美！然而，现实的世界告诉我；理想的饱满一定要遇到拥有相同理想的另一半！我喜欢珠海，一个美丽的花园城市；我喜欢那里的天气，没有北方的寒冷；四季如春的温度感觉非常惬意，不用担忧换季带来的差异！走在市区的街道上，绿化的花草树木被园丁修剪的井然有序；形态各异的花卉搭配得格外美观！尤其是除过草之后的绿地，泥土的芬芳与绿草的清新扑鼻而来，有一种身处大草原的感觉，使人心旷神怡！我时常一个人发愣，散步；看着过往的人群，车水马龙的街道；也时常去繁华的街巷，拥挤的商业中心；感觉这才是生活，正因为世界有了这么多事物的陪伴，才使我有了对美好生活的向往与喜悦！珠海的夜，很美；到处灯红酒绿，一派歌舞升平的祥和；每当夜幕降临，才是广东因有的生活的开始！溜冰场，酒吧，迪厅，大排档等等等等；我很庆幸在这里认识了很多人，他们教会了我很多，也帮助了我很多；我们都是来自五湖四海，为了同一个目标而聚集在一起的年轻人；我们时常出去聚会，嗨皮；但等到散场后，又回到了应有的孤寂！白天，可以去渔女，公园，九州城，免税店等等都是不错的地方！人常说，一个时代会有一个时代的代表；而我在这个曾经为之奋斗的地方，也时常会想起曾经相识的人，走过的地方，看过的风景；有时候，听着当时的流行歌曲，也会感伤；也会自嘲一笑；还有那公车到站的粤语提醒，还有那想见却永远没见的人；一篇篇，一幕幕久久回荡在脑海；早晨的肠粉，中午的餐饭，下午的炒粉，晚上的烧烤；好似味道还回味在口中一样！人，只有在对自己真诚的人的眼里，才会感觉到亲切；而我，也着实喜欢这座城市带给我家一样的温暖感觉！在这短暂而悠长的时光里，我成长了很多，也磨砺了很多；正是因为思想的成熟，阅历的增长，我选择了离开；去寻找属于自己的新的天地，新的开始，新的征程！其实，无论走过多少地方；都不重要！重要的是你从中得到什么！知识！阅历！思想！每个人，在人生的道路上；难免遇到挫折困苦，也难免会因为一些因素而错失机缘！不可能因为一时的艰难险阻而放弃将要来临的幸福！也不可能因为一时的过失而自暴自弃颓废一生！人，应该用豁达的心态来迎接下一秒的新鲜时光；而不是沉溺在上一秒的懊恼当中！每个人的路，都在自己的脚下；只有自己醒悟才能把未来的路走好，反之只会让错误延续到未来，从而影响以后的健康生活！即便曾经的时光再美好，那也只是人生道路上的一段插曲；没必要去纠结当时的愕然，愚昧！就像我，从来不对上一秒的事情产生情绪一样！一切都是恬淡的样子，顺其自然比什么都好！对于未来，只要真诚的去善待身边的所有；我相信，未来的时光，也该是你想象的模样！蒲公英家乡的茶籽林坐落在戴云山脉西麓的高才坂，属亚热带季风气候区，夏无酷暑，冬无严寒，日照充足，雨量充分，山区丘陵满地尽是红壤土，非常适宜茶籽树的生长。高才坂种植小果油茶有着悠久的历史，是远近闻名的茶籽油之乡。家乡高才坂，一年四季茶籽林郁郁葱葱，枝繁叶茂。村头的亭后坑、银珠垄、赤土岭、牛脊崎，村尾的庵墘头、虎坪林、下淂，村庄对岸的牌匾山、坑里、墘头、下坋、坑柄里等等，山坡上，山坳里，道路边，田边地头，屋后山边，漫山遍野到处是一片连着一片的茶籽林。那里是我儿时与伙伴们捉迷藏、摘茶苞、采茶菇、捡茶籽的地方。每当春风拂来，几场淅淅沥沥的春雨之后，唤醒沉睡了一个冬季的茶籽树林。老茶树开始发出新枝，抽出嫩芽，嫩芽吐露出嫩红嫩红的叶片，转眼间，嫩红的叶片又变成稚嫩的绿叶。整片茶籽林绿浪涛涛，层层叠叠，在家乡群山环抱的山腰上，形成一道翠绿的屏障。清明节后，儿时的我常与伙伴们在嬉戏玩耍的同时，十分注意寻找茶籽树梢上的“茶苞，这是一种生长在茶籽树上的果实，果熟时外表会脱去一层薄如蝉翼的白皮，淡绿色的形似胖胖的寿桃，中空，果瓤可以食用，果肉脆而汁多，清甜爽口。“茶苞是儿时伙伴们最喜欢的果实，从茶籽树上摘下，在袖口上来回擦几下，脱去表层酥松的外皮，馋猫似地往嘴里塞，津津有味地品尝着大自然恩赐的美食，这是我与伙伴们喜欢到茶籽林玩耍的原因之一。秋季来临，茶籽树上挂满了青色中夹杂着褐色的茶籽果，茶树枝被压弯下垂，这是村民一年的希望。全村的村民这时节荷锄上山为茶籽林锄草，将林地里各种杂草锄掉，并填埋在茶籽树头下作为有机肥，锄后的茶籽林寸草不留。这是家乡当地的传统习惯，很少采撷树上的油茶果，而是在锄得干干净净的林地上捡茶籽。村民在锄草中，时常发现茶籽林里长的一种真菌茶树菇，菇伞灰色如碗口大，菇腿灰白色很长，采摘回家煮汤或煮米粉汤味道极其甜美。清爽的秋风送来百花仙子的柔情蜜意，吹开了丹桂的花骨朵，让神州大地香气四溢的同时，茶籽树也毫不犹豫地绽放自己的花朵，展示自己最妖艳的容貌，一夜之间，漫山遍野的茶籽林中雪白的油茶花盛开了，白色花朵中间吐露出金黄色的花蕊，散发出沁人心脾的芬芳，茶籽林变成一片白色的花海。成群的蜜蜂“嗡嗡嗡在花丛中飞来飞去，落在金黄色的花蕊中不知疲倦地采蜜，也为油茶花义务传授花粉，为明年茶籽树挂果立下汗马功绩。儿时，我和伙伴们像一群快乐的小蜜蜂，一头扎进茶籽林里，一边欣赏着洁白娇艳的油茶花，一边折一根抽去内心的赤蕨杆当吸管，插入金黄色的花蕊中，轻轻一吸，芬芳甜美、味道香醇的花蜜便进入口中。我们小心翼翼地攀下茶树枝，如痴如醉地在一朵又一朵的油茶花中滋滋有声吮吸着花蜜，比供销社卖的硬糖粒还要甜美十倍。到了秋高气爽的秋末，山区空气相对枯燥，白天依然烈日炎炎，可夜晚却出现霜冻，昼夜温差很大。这时，茶籽树上的茶籽果由原来的青色转瞬间全部变成深褐色，已经熟透的茶籽果一颗颗裂开大嘴，露出大嘴里油光发亮的油茶籽。阵阵秋风送爽，茶籽树梢随风摇曳，催促油茶籽快快离开树梢，洒脱地坠落在村民锄得干干净净的地板上，几天时间，茶树林的地面上便铺上一层深褐色的油茶籽。此时的茶籽林沸腾了，满怀丰收喜悦的村民，发动全村男女老幼一起上山捡收油茶籽，大家一边欢快地捡着，一边大声地说笑着，这边有母亲唤儿声，那边有青年男女对歌声，茶籽林里飘出一阵阵欢乐的笑声。这笑声就像嘹亮的集合号角，将满地的油茶籽在愉快的气氛中快速聚结起来，坚决果断地跟随村民进入农家大院。(油茶籽从开花、授粉、结果到成熟落地，经历了秋、冬、春、夏、秋五个季节的阳光雨露，尽吸天然养分，天地精华，营养极高，是纯天然的绿色食品。村民视油茶籽为农家之宝，及时晒干，装筐储藏，等待冬闲之时送到榨油坊加工成金黄色的茶籽油。