Coder Space

PKU 1742 Coins --- 完全背包

题意:通过指定数量的不同面值零钱,问能凑出从1到m之间钱数的个数。

解法:做这个题时,最初是使用的背包九讲中多重背包的二进制划分转化成01背包这个时间复杂度为O(V*∑log(n[i]))的方法来做,结果TLE了。
            后来把问题看成完全背包问题的变种,利用数组标签的方法解决,复杂度为O(VN)。


源代码

posted on 2010-11-29 17:38 David Liu 阅读(121) 评论(0)  编辑 收藏 引用 所属分类: 动态规划


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


My Links

Blog Stats

常用链接

留言簿

文章分类

文章档案

搜索

最新评论