贪心算法实验求解背包问题

1、算法分析与设计实验报告第 四 次实验姓名学号班级时间10.17上午地点工训楼309 实验名称贪心算法实验(求解背包问题)实验目的通过上机实验，要求掌握贪心算法的问题描述、算法设计思想、程序设计。实验原理给定任意几组数据，利用贪心算法的思想，将物品装入背包并使得其价值最大。程序思路：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1in。（1） 首先将单位重量的平均价值排序。（2） 根据背包容量依次将平均价值高的物品放入背包中。实验步骤（1）首先计算每种物品单位重量的价值vi/wi；（2）依贪心选择策略，将尽可能多的单位重量价值最高的物品装

2、入背包；（3）若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包；（4）依此策略一直地进行下去，直到背包装满为止。关键代码bool comparison(st a,st b) /自定义函数说明sort函数使用的模式是从大到小排序 return a.perval>b.perval; void Knapsack(int n,float m,st item,float x)int i;float temN; /该变量数组用来记录排好序之后的物品是否被放入背包float tmpN; /定义一个数组用来保存以前的编号及重量，用于构造最优解for

3、(i=0;i<n;i+)tmpi=itemi.w;sort(item,item+n,comparison); /实现单位重量的平均价值的物品的排序for(i=0;i<n;i+) /初始化数组x及temxi=0,temi=0;float c=m;for(i=0;i<n;i+) /物品整件被装下，则xi=1;if(itemi.w>c)break;temi=1;c-=itemi.w;if(i<n) /物品只有部分被装下temi=c/itemi.w;for(i=0;i<n;i+) /将排好序的物品编号与原始编号匹配for(int j=0;j<n;j+) /构造

4、最优解if(itemi.w=tmpj)xj=temi;测试结果输入较小的结果： 输入较大的结果： 实验心得首先这个实验，需要注意的点是背包问题与0-1背包不同，物品可以部分的放入背包中，所以思路也不一样，首先就是将物品按照单位质量价值排序，只这一点就有一点难度。难度在于要是排序后物品的编号就会发生改变，输出的就不是之前的编号的物品，导致错误，后来发现如果为每一个物品保存一个副本，然后将它们的编号进行对比，就可以进行正确的输出了。其中这个实验让我学到了两点：一是结构体的使用，之前一直没有怎么用过，现在才发现自己其实不会用；二十对于库函数sort函数的使用。感觉每一次实验都有学到东西，很开心。实验

5、得分助教签名附录：完整代码（贪心法）/贪心算法 背包问题#include<iostream>#include<algorithm>#include<time.h>#include<iomanip>using namespace std;const int N=10000;struct st /定义结构体，用来存放和物品相关的变量float v;float w;float perval;void Knapsack(int n,float m,st item,float x); /声明贪心算法求解问题函数int main()float m; int

6、n,i;cout<<"请输入背包的容量："cin>>m;cout<<"请输入物品的个数："cin>>n;st itemN; float xN+1;cout<<"待装物品的重量为："<<endl;for(i=0;i<n;i+)cin>>itemi.w;cout<<endl;cout<<"待装物品的价值为："<<endl;for(i=0;i<n;i+)cin>>itemi.v;

7、cout<<endl;/计算每一个物品的单位重量的价值for(i=0;i<n;i+)itemi.perval=itemi.v/itemi.w;clock_t start,end,over; /计算程序运行时间的算法start=clock();end=clock();over=end-start;start=clock(); Knapsack(n,m,item,x); /调用贪心算法函数cout<<"选?择?装Á¡ã下?的Ì?物?品¡¤的Ì?比À¨¨例

8、64;y如¨?下?：êo"<<endl; /输出最优解编号及比例for(i=0;i<n;i+)cout<<""<<i+1<<":"<<xi<<endl;end=clock();printf("The time is %6.3f",(double)(end-start-over)/CLK_TCK); /显示运行时间system("pause");return 0; bool comparison(st a,st

9、 b)/自定义函数说明sort函数使用的形式是从大到小排序 return a.perval>b.perval; void Knapsack(int n,float m,st item,float x)int i;float temN; /该变量数组用来记录排好序之后的物品是否被放入背包float tmpN; /定义一个数组用来保存以前的编号及重量，用于构造最优解for(i=0;i<n;i+)tmpi=itemi.w;sort(item,item+n,comparison); /实现单位重量的平均价值的物品的排序for(i=0;i<n;i+) /初始化数组x及temxi=0,temi=0;float c=m;for(i=0;i<n;i+) /物品整件被装下，则xi=1;if(itemi.w>c)brea