实验报告 贪心背包

PAGEPAGE6《算法设计与分析》实验报告五学号：1004091130姓名：金玉琦日期：2011-11-10得分：实验内容：应用贪心算法求解背包问题二、所用算法的基本思想及复杂度分析：1.贪心法贪心法是把一个复杂问题分解为一系列较为简单的局部最优选择,每一步选择都是对当前解的一个扩展,直到获得问题的完整解。贪心法的典型应用是求解最优化问题,而且对许多问题都能得到整体最优解,即使不能得到整体最优解,通常也是最优解的很好近似。背包问题基本思想给定n种物品和一个容量为C的背包,物品i的重量是w,价值为v,背包问题是如何选择装入背包的物品,使得装入背包中物品的总价值最大。有3种看似合理的贪心策略：(1)选择价值最大的物品,因为这可以尽可能快地增加背包的总价值。但是,虽然每一步选择获得了背包价值的极大增长,但背包容量却可能消耗得太快,使得装入背包的物品个数减少,从而不能保证目标函数达到最大。(2)选择重量最轻的物品,因为这可以装入尽可能多的物品,从而增加背包的总价值。但是,虽然每一步选择使背包的容量消耗得慢了,但背包的价值却没能保证迅速增长,从而不能保证目标函数达到最大。(3)以上两种贪心策略或者只考虑背包价值的增长,或者只考虑背包容量的消耗,而为了求得背包问题的最优解,需要在背包价值增长和背包容量消耗两者之间寻找平衡。正确的贪心策略是选择单位重量价值最大的物品。应用第3种贪心策略,每次从物品集合中选择单位重量价值最大的物品,如果其重量小于背包容量,就可以把它装入,并将背包容量减去该物品的重量,然后我们就面临了一个最优子问题———它同样是背包问题,只不过背包容量减少了,物品集合减少了。因此背包问题具有最优子结构性质。2）复杂度分析算法的时间主要消耗在将各种物品依其单位重量的价值从大到小排序。因此,算法其时间复杂性为O(nlog2n)。三．源程序及注释：#defineMAX100#include<TIME.H>#include<IOSTREAM>#include<algorithm>usingnamespacestd;//设计物品属性，重量和价值structThings{ doublew; //记录重量 doublev; //记录价值};//按单位价值降序排列intcmp(Thingsa,Thingsb){ returna.v/a.w>b.v/b.w;}//贪心法背包问题函数doubleBag_Value(Thingsa[],intc,intn){ doublebag_val1=0,bag_val2=0; inti=0; doubleweight_sum=0; for(intj=0;j<n;j++) //求出所有物品的重量和 { weight_sum+=a[j].w; bag_val2+=a[j].v; } if(weight_sum<=c) //所有物品小于容量，直接输出结果 { cout<<"将所有物品放入背包"<<endl; returnbag_val2; } else //重量和大于背包容量，贪心法求解 { sort(a,a+n,cmp); while(a[i].w<=c) { if(a[i].w<=c) { c=c-a[i].w; bag_val1+=a[i].v; cout<<"价值为"<<a[i].v<<"的物品放入" <<a[i].w<<endl; } i++; } if(c) { cout<<"价值为"<<a[i].v<<"的物品放入"<<c<<endl; bag_val1+=a[i].v/a[i].w*c; } returnbag_val1; }}voidmain(){ Thingst[MAX]; inti,n,c; intresult; cout<<"输入物品总数:"; cin>>n; cout<<"输入背包的总容量:"; cin>>c; srand(time(0)); for(i=0;i<n;i++) { t[i].w=rand()/55; t[i].v=rand()/55; cout<<"第"<<i+1<<"个物品重量:"<<t[i].w <<"价值:"<<t[i].v<<endl; } cout<<"结果"<<endl; result=Bag_Value(t,c,n); cout<<"背包总价值:"<<result<<endl;}四、运行输出结果：五、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训：背包问题与0/1背包问题类似,这两类问题都具有最优子结构性质,所不同的是背