ACM竞赛之FatMouse' Trade 贪心法
需积分: 50 56 浏览量
2010-08-26
13:20:46
上传
评论 1
收藏 63KB DOC 举报
FatMouse' Trade
、题目描述
问题主要是说一只老鼠有 磅猫食，然后在 个房间
里面用猫食换 ，房间 中有 磅的猫食来换 磅的 ，
而且老鼠可以在一个房间里根据一定比例 来换取
问：如何兑换，才能使得 所换取到的 最多。
、与部分背包问题归约
分析本题，不难发现，如果把 磅猫食与部分背包问题中背包容量，在每
个房间与背包问题中的物品相对应，而每个房间的 磅猫食对应背包问题中
的物品所占用背包的体积，而所获得的 磅 对应到背包问题中物
品的价值
通过上述映射关系的转换，可以将 问题归约到经典的部分背包
问题，通过贪心算法来解决这个问题，最终得到答案。
、 的贪心解法
本题的解决方案是：优先选择 最大的房间进行换取，如果能够完全
换取则完全换取，否则仅换取一部分；如此操作，直到耗尽 磅猫食为止。
、示例解题源代码
!"
#$%
&
#'
'
())'
*))'
+))'
(#,'
*#,'
+#,'
+#'
'
('
-!$*$../0#/0%1234001$22500#225%%
&
*$2' 2'66%
&
*$../0(/0*%'
2$+%(*'
7
*$2' 2'66%
*$(26'( 2'(66%
*$("%
&
剩余10页未读，继续阅读
资源评论
