版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、ACM程序设计竞赛入门,浙江工业大学田贤忠2020/7/30,1,2020/7/30,2,第七讲,贪心算法(贪婪算法),2020/7/30,3,什么是贪心算法?2020/7/30,4,所谓贪心算法 :在对问题求解时,采用逐步构造最优解。也就是说,它要求贪心地选择最佳操作,并希望通过一系列局部的最优选择,能够产生一个整个问题的(全局(最优解。决策一旦作出,就不能更改。作为贪婪决策的依据称为贪心准则(贪婪标准),2020/7/30,5,一个简单例子,FatMouse Trade,2020/7/30,6,HDOJ: 1009FatMouse Trade,2020/7/30,7,问题描述FatMous
2、e准备了M磅猫粮,准备与看守仓库的猫进行交易,仓库里有他最喜欢的食物JavaBean .仓库有N个房间。第一个房间里有几磅的JavaBeans,需要几磅的猫粮FatMouse .并不需要用房间里所有的JavaBeans来交换,相反,如果他支付一磅猫粮,他可能会得到一磅JavaBeans .这里a是一个实数。现在他给你布置了这个作业,告诉他他能获得的最大数量的JavaBeans .2020/7/30,8,输入:输入由多个测试用例组成。每个测试用例以包含两个非负整数M和N的一行开始,然后是N行,每一行分别包含两个非负整数纪和Fi .最后一个测试用例后面是两个1 .所有整数都不大于1000 .输出:
3、对于每个测试用例,在一行中打印一个精确到小数点后3位的实数,这是FatMouse可以获得的最大JavaBeans数量2007年.样本输入5 3 (5个,有3个交换的地方)7 2 (2换7) 4 3 5 2 20 3 25 18 24 15 15 10 -1 -1,样本输出13.333 31.500,2020/7/30,9,贪心准则:很明显,每次总是先挑最划算的交易,一直把手里的猫粮都换完,2020/7/30,10,算法基本思想:输入(其中,交易数据j,F对放入数组(对数组排序(按效益,降序(按效益高低进行有序交易,一直把手里的猫粮都换完。输出得到的爪哇豆2020年7月30日,11,部分参考代码:结构、仓库、豆类、食品;双r;a1001号仓库;2020/7/
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- GB/T 13929-2024水环真空泵和水环压缩机试验方法
- 物业公司运营管理方案(2篇)
- 2023年汽车自动采样设备资金筹措计划书
- 华夏文化五千年-知到答案、智慧树答案
- 2023年卫星传输服务投资申请报告
- 2023年电缆网设备资金筹措计划书
- 2024年腐乳项目资金申请报告
- 2024年加气机项目资金筹措计划书代可行性研究报告
- 2024年非临床安全性评价服务项目资金申请报告代可行性研究报告
- 公司年度工作总结及协同合作
- 联通(中级)智网工程师理论考试题库及答案
- (正式版)HGT 6313-2024 化工园区智慧化评价导则
- 《电力物资绿色包装技术规范》
- 二级公立医院绩效考核三级手术目录(2020版)
- 小学数学大单元教学设计策略
- 竹子作为制浆造纸原料的优势
- iso9001质量管理体系过程清单
- 个人简历(3)(最新整理)
- 个人简历简洁版[共1页]
- 普通高等学校毕业生就业协议书(三方协议)
- 新版人教部编版语文九年级上册生字词[带拼音与释义]
评论
0/150
提交评论