PKU 1742 Coins --- 完全背包

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

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

源代码

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

只有注册用户登录后才能发表评论。


相关文章: PKU 1015 Jury Compromise --- 动态规划 PKU 3260 The Fewest Coins --- 完全背包 + 01背包 PKU 2063 Investment --- 完全背包 PKU 3132 Sum of Different Primes ---01背包 PKU 3624 Charm Bracelet ---01背包 PKU 1882 Stamps --- 完全背包 PKU 1384 Piggy-Bank --- 完全背包 PKU 1742 Coins --- 完全背包 PKU 2394 Space Elevator --- 分组背包 PKU 1276 Cash Machine --- 多重背包

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

Coder Space