本题为多重背包问题,即每种零钱的个数是有限个,求不超过目标钱数的可以组合出的最大钱数
采用DP的思想,先对目标钱数以内的所有面额做逆向遍历,初始dp[0] = true,即0元可凑出
在此基础上如果当前的stat可以凑出,那么继续组合出更大的钱数,记下当前有限个零钱和前面的
零钱一起可以凑出的不超过目标钱数的所有合法的值。最后从money逆向打印记下的最大的值即可
Source Code
Problem: 1276
|
|
User:
yangliuACMer
|
Memory: 640K |
|
Time: 516MS |
Language: C++ |
|
Result: Accepted
|
分享到:
相关推荐
这里我把自己对poj1276的理解和分析还有源代码都放在了里面,希望对大家有所帮助。谢谢
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
北大POJ初级-动态规划 解题报告+AC代码
北大POJ1276试题代码
北大POJ1276-Cash Machine 解题报告+AC代码
poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...
PKU Online Judge上面很全面的动态规划试题总结。动态规划是ACM考点中最重要的一大类算法之一,对于工作人员来说,动态规划也是实际开发中经常会遇到的算法。这是POJ上面很多DP题目的总结与深刻分析。利于算法学习,...
北大POJ1015-Jury Compromise【动态规划DP】 解题报告+AC代码
晒代码之二——多重背包(POJ1276)
动态规划算法poj1088滑雪实验报告 动态规划算法poj1088滑雪实验报告
关于poj dp分类,我一直寻找dp的分类,终于找到了,也上传一下
POJ上的DP分类: 容易: 1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1208, 1276, 1322, 1414, 1456, 1458, 1609, 1644, 1664, 1690, 1699, 1740(博弈), 1742, 1887, 1926(马尔科夫矩阵,求...
组合数学 ACM 和,POJ里用到组合数学的题目
经典的0-1背包问题. 适合新手学习. 原题网址:http://poj.grids.cn/problem?id=2773
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
放炮问题,北大网站 POJ 1185 算法
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ1321棋盘问题 很好两种解法很值得去参考一下 完整的实验报告还有代码希望kan
poj online judge 1050 最大子矩阵动态规划解决