背包小记

今天做了一下背包专题,连接http://acm.hust.edu.cn:8080/judge/contest/view.action?cid=10736#overview密码是:sduacm 个人觉得这几题都很不错
额,第一题就不说了,普通的0-1背包

G题(HDU4091)是2011年上海区预赛第一题,据说AC这道题就可以拿铜牌了(囧) 题意是给俩个物品,每个物品有价值和体积,显然直接贪心不对,可以当作背包来解,但背包的容量很大,不能直接背包。这题的做法是:现求总容量对俩个物品的体积的LCM取余的余数,然后在余数中枚举,对其他的容量贪心,很容易证明这个思路的正确性。
HDU4091

I题(SGU259)单机调度问题,题意是只有一个打印机,有许多传单需要打印和分发,打印的时间T[i],分发的时间是L[i],每个传单必须先打印后分发,假设有很多分发员,问将左右的传单打印并且分发完所用完的最短时间。这题直观有个感觉就是因为分发员有很多人,分发时间长的传单显然先打印比较好,并且很容易证明这个贪心思想的正确性。因此对L从大到小排序,然后再求的时间就是最短的时间。
SGU259

SPOJ39_PIGBANK:这题是个经典的完全背包问题,题意是有个储蓄罐,知道了空的时候的质量和装满硬币的质量,给了一些硬币的质量和价值,求储蓄罐装满时硬币的最小价值。
经典题。
SPOJ39_PIGBANK






posted on 2012-08-04 18:05 phonism 阅读(138) 评论(0)  编辑 收藏 引用 所属分类: 动态规划


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2020年9月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

统计

常用链接

留言簿

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜