贪心算法实验(求解背包问题)_第1页
贪心算法实验(求解背包问题)_第2页
贪心算法实验(求解背包问题)_第3页
贪心算法实验(求解背包问题)_第4页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

贪心算法实验(求解背包问题)贪心算法实验(求解背包问题)贪心算法实验(求解背包问题)资料仅供参考文件编号：2022年4月贪心算法实验(求解背包问题)版本号：A修改号：1页次：1.0审核：批准:发布日期：算法分析与设计实验报告第四次实验姓名学号班级时间上午地点工训楼309实验名称贪心算法实验(求解背包问题)实验目的通过上机实验，要求掌握贪心算法的问题描述、算法设计思想、程序设计。实验原理给定任意几组数据，利用贪心算法的思想，将物品装入背包并使得其价值最大。程序思路：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。首先将单位重量的平均价值排序。根据背包容量依次将平均价值高的物品放入背包中。实验步骤（1）首先计算每种物品单位重量的价值vi/wi；（2）依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包；（3）若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包；（4）依此策略一直地进行下去，直到背包装满为止。关键代码boolcomparison(sta,stb){; sort(item,item+n,comparison);>c) break; tem[i]=1; c-=item[i].w; } if(i<n); for(i=0;i<n;i++)==tmp[j]) x[j]=tem[i]; } }}测试结果输入较小的结果：输入较大的结果：实验心得首先这个实验，需要注意的点是背包问题与0-1背包不同，物品可以部分的放入背包中，所以思路也不一样，首先就是将物品按照单位质量价值排序，只这一点就有一点难度。难度在于要是排序后物品的编号就会发生改变，输出的就不是之前的编号的物品，导致错误，后来发现如果为每一个物品保存一个副本，然后将它们的编号进行对比，就可以进行正确的输出了。其中这个实验让我学到了两点：一是结构体的使用，之前一直没有怎么用过，现在才发现自己其实不会用；二十对于库函数sort函数的使用。感觉每一次实验都有学到东西，很开心。实验得分助教签名附录：完整代码（贪心法）; cout<<endl; cout<<"待装物品的价值为："<<endl; for(i=0;i<n;i++) cin>>item[i].v; cout<<endl; erval=item[i].v/item[i].w; clock_tstart,end,over;; sort(item,item+n,comparison);>c) break; tem[i]=1; c-=item[i].w; } if(i<

人人文库> 全部分类> 教育资料 > 备课教案

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论