| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 6950 人关注过本帖, 1 人收藏
标题:动态规划 ——找零钱
取消只看楼主 加入收藏
编译中。。
Rank: 7Rank: 7Rank: 7
来 自:中国
等 级:黑侠
帖 子:198
专家分:511
注 册:2011-7-29
结帖率:75%
收藏(1)
已结贴  问题点数:100 回复次数:6 
动态规划 ——找零钱
描述
我们知道人民币有1、2、5、10、20、50、100这几种面值。
现在给你n(1≤n≤250)元,让你计算换成用上面这些面额表示且总数不超过100张,共有几种。
比如4元,能用4张1元、2张1元和1张2元、2张2元,三种表示方法。
输入
输入有多组,每组一行,为一个整合n。
输入以0结束。
输出
输出该面额有几种表示方法。
样例输入
1
4
0
样例输出
1
3


想半天不知道用DP怎么写,求代码一定要带上注释啊。。。
              最近学的有的郁闷,卡了一天,希望能有人指点一下。
搜索更多相关主题的帖子: 人民币 动态 
2014-12-01 12:52
编译中。。
Rank: 7Rank: 7Rank: 7
来 自:中国
等 级:黑侠
帖 子:198
专家分:511
注 册:2011-7-29
收藏
得分:0 
。。继续求大神

 当我感到些许疲倦时   便想躺在阳光下,小路旁 . 可这些往往都是奢望..
2014-12-01 23:08
编译中。。
Rank: 7Rank: 7Rank: 7
来 自:中国
等 级:黑侠
帖 子:198
专家分:511
注 册:2011-7-29
收藏
得分:0 
最近比较忙,3天没来论坛,看到大家回复,先结帖 在好好理解一下

 当我感到些许疲倦时   便想躺在阳光下,小路旁 . 可这些往往都是奢望..
2014-12-04 14:03
编译中。。
Rank: 7Rank: 7Rank: 7
来 自:中国
等 级:黑侠
帖 子:198
专家分:511
注 册:2011-7-29
收藏
得分:0 
回复 6 楼 巧若拙
你的注释很棒,否则根本看不懂版主大人的回复。我再加一个我自己的理解吧。

程序代码:
f[k][j] += f[k-a[i]][j-1];  //这里是最关键的,也是动态规划的核心,
下面是我调试理解这个程序的时候,打印出来的结果。我分析之后才明白,
比如 f[2][1]+=f[1][0]]=0   表示当子问题为金额2元时,用1张纸币如何获得最优解
因为之前已经包含了一张a[i]元的纸币,这里a[i]=1,所以这个子问题的最优解就是,去掉
a[i]元钱(1元钱)和去掉a[i]元钱的容量(即一张)的最优解。。 
从小规模循环至答案。




4
f[1][1]+=f[1-a[0]][1-1]]=1
f[1][1]+=f[0][0]]=1
f[2][1]+=f[2-a[0]][1-1]]=0
f[2][1]+=f[1][0]]=0
f[2][2]+=f[2-a[0]][2-1]]=1
f[2][2]+=f[1][1]]=1
f[3][1]+=f[3-a[0]][1-1]]=0
f[3][1]+=f[2][0]]=0
f[3][2]+=f[3-a[0]][2-1]]=0
f[3][2]+=f[2][1]]=0
f[3][3]+=f[3-a[0]][3-1]]=1
f[3][3]+=f[2][2]]=1
f[4][1]+=f[4-a[0]][1-1]]=0
f[4][1]+=f[3][0]]=0
f[4][2]+=f[4-a[0]][2-1]]=0
f[4][2]+=f[3][1]]=0
f[4][3]+=f[4-a[0]][3-1]]=0
f[4][3]+=f[3][2]]=0
f[4][4]+=f[4-a[0]][4-1]]=1
f[4][4]+=f[3][3]]=1
f[2][1]+=f[2-a[1]][1-1]]=1
f[2][1]+=f[0][0]]=1
f[2][2]+=f[2-a[1]][2-1]]=1
f[2][2]+=f[0][1]]=1
f[3][1]+=f[3-a[1]][1-1]]=0
f[3][1]+=f[1][0]]=0
f[3][2]+=f[3-a[1]][2-1]]=1
f[3][2]+=f[1][1]]=1
f[3][3]+=f[3-a[1]][3-1]]=1
f[3][3]+=f[1][2]]=1
f[4][1]+=f[4-a[1]][1-1]]=0
f[4][1]+=f[2][0]]=0
f[4][2]+=f[4-a[1]][2-1]]=1
f[4][2]+=f[2][1]]=1
f[4][3]+=f[4-a[1]][3-1]]=1
f[4][3]+=f[2][2]]=1
f[4][4]+=f[4-a[1]][4-1]]=1
f[4][4]+=f[2][3]]=1
3

 当我感到些许疲倦时   便想躺在阳光下,小路旁 . 可这些往往都是奢望..
2014-12-04 14:50
编译中。。
Rank: 7Rank: 7Rank: 7
来 自:中国
等 级:黑侠
帖 子:198
专家分:511
注 册:2011-7-29
收藏
得分:0 
动态规划很难,对于我来说给出转移方程说不定也写不了。,,

 当我感到些许疲倦时   便想躺在阳光下,小路旁 . 可这些往往都是奢望..
2014-12-04 14:51
编译中。。
Rank: 7Rank: 7Rank: 7
来 自:中国
等 级:黑侠
帖 子:198
专家分:511
注 册:2011-7-29
收藏
得分:0 
提交之后还是Wrong Answer 。。。。

 当我感到些许疲倦时   便想躺在阳光下,小路旁 . 可这些往往都是奢望..
2014-12-04 14:54
编译中。。
Rank: 7Rank: 7Rank: 7
来 自:中国
等 级:黑侠
帖 子:198
专家分:511
注 册:2011-7-29
收藏
得分:0 
ok,Accepted的了,  感谢啊。  动态规划,我得好好练习一下

 当我感到些许疲倦时   便想躺在阳光下,小路旁 . 可这些往往都是奢望..
2014-12-04 14:57
快速回复:动态规划 ——找零钱
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.040364 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved