没有合适的资源?快使用搜索试试~ 我知道了~
ACM竞赛之FatMouse' Trade 贪心法
需积分: 50 11 下载量 164 浏览量
2010-08-26
13:20:46
上传
评论 1
收藏 63KB DOC 举报
温馨提示
试读
11页
FatMouse' Trade问题主要是说一只老鼠有M磅猫食,然后在N个房间里面用猫食换JavaBean,房间i中有F[i]磅的猫食来换J[i]磅的JavaBean,而且老鼠可以在一个房间里根据一定比例a%来换取JavaBean. 问:如何兑换,才能使得FatMouse所换取到的JavaBean最多。
资源推荐
资源详情
资源评论
FatMouse' Trade
、题目描述
问题主要是说一只老鼠有 磅猫食,然后在 个房间
里面用猫食换 ,房间 中有 磅的猫食来换 磅的 ,
而且老鼠可以在一个房间里根据一定比例 来换取
问:如何兑换,才能使得 所换取到的 最多。
、与部分背包问题归约
分析本题,不难发现,如果把 磅猫食与部分背包问题中背包容量,在每
个房间与背包问题中的物品相对应,而每个房间的 磅猫食对应背包问题中
的物品所占用背包的体积,而所获得的 磅 对应到背包问题中物
品的价值
通过上述映射关系的转换,可以将 问题归约到经典的部分背包
问题,通过贪心算法来解决这个问题,最终得到答案。
、 的贪心解法
本题的解决方案是:优先选择 最大的房间进行换取,如果能够完全
换取则完全换取,否则仅换取一部分;如此操作,直到耗尽 磅猫食为止。
、示例解题源代码
!"
#$%
&
#'
'
())'
*))'
+))'
(#,'
*#,'
+#,'
+#'
'
('
-!$*$../0#/0%1234001$22500#225%%
&
*$2' 2'66%
&
*$../0(/0*%'
2$+%(*'
7
*$2' 2'66%
*$(26'( 2'(66%
*$("%
&
#,2'
2('
(2#,'
(#,2('
(2(('
((2(#,'
*#,2*'
*2*('
*(2*#,'
7
#2)'
*$2' 2'66%
&
*$#"*%
&
#2(6#'
#2#5*'
7
&
#2#68#'
+9'
7
7
,*$.*:./#%'
7
)'
7
本代码中,选取 比值最大的时候,可以如此处理:通过将 与 绑定为一个
结构体,
;
&
('
*'
7
输入之后,通过自定义的比较函数,根据 (* 的比值进行排序,进而改进代码。
今年暑假不 AC
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K
(Java/Others)
Total Submission(s): 4431 Accepted Submission(s): 2387
<+#=,
>今年暑假不 ?@?”
>是的。”
>那你干什么呢?”
>看世界杯呀,笨蛋!”
>ABC08D
确实如此,世界杯来了,球迷的节日也来了,估计很多 ?@ 也会抛开电脑,
奔向电视了。
作为球迷,一定想看尽量多的完整的比赛,当然,作为新时代的好青年,你一
定还会看一些其它的节目,比如新闻联播(永远不要忘记关心国家大事)、非
常 E6F、超级女生,以及王小丫的《开心辞典》等等,假设你已经知道了所有
你喜欢看的电视节目的转播时间表,你会合理安排吗?(目标是能看尽量多的
完整节目)
G,
输入数据包含多个测试实例,每个测试实例的第一行只有一个整数
$ 2))%,表示你喜欢看的节目的总数,然后是 行数据,每行包括两个
数据 H/H$ 2 2%,分别表示第 个节目的开始和结束时间,为了简
化问题,每个时间都用一个正整数表示。2) 表示输入结束,不做处理。
4,
对于每个测试实例,输出能完整看到的电视节目的个数,每个测试实例的输出
占一行。
;#,G,
)F
I
剩余10页未读,继续阅读
资源评论
zhengtuozhan
- 粉丝: 0
- 资源: 11
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功