换钱问题# CS - 计算机科学
c*d
1 楼
给你 x cents ， 让你换成50, 25, 10, 5, 1 cent, 问有多少种换法？
用dynamic programming 解决。我想了很久， 不知道怎么做。请大虾指教
，并希望解释详细一些。我主要是对于分解问题想不清。谢谢
用dynamic programming 解决。我想了很久， 不知道怎么做。请大虾指教
，并希望解释详细一些。我主要是对于分解问题想不清。谢谢
c*t
2 楼
a very typical problem using dynamic programming. Search "coin changing"
"dynamic programing" in google.
【在 c****d 的大作中提到】
: 给你 x cents ， 让你换成50, 25, 10, 5, 1 cent, 问有多少种换法？
: 用dynamic programming 解决。我想了很久， 不知道怎么做。请大虾指教
: ，并希望解释详细一些。我主要是对于分解问题想不清。谢谢
"dynamic programing" in google.
【在 c****d 的大作中提到】
: 给你 x cents ， 让你换成50, 25, 10, 5, 1 cent, 问有多少种换法？
: 用dynamic programming 解决。我想了很久， 不知道怎么做。请大虾指教
: ，并希望解释详细一些。我主要是对于分解问题想不清。谢谢
c*d
3 楼
Yeah, it is a very typical problem. Maybe when I studied dynamic programming,
I was restricted my mind within some "optimal" solution questions. Most time
the examples are talking about how to change money with minimal number of
coins. Actually I sought in google, I got the answer and source code, but
still don't understand why.
;)
【在 c****t 的大作中提到】
: a very typical problem using dynamic programming. Search "coin changing"
: "dynamic programing" in google.
I was restricted my mind within some "optimal" solution questions. Most time
the examples are talking about how to change money with minimal number of
coins. Actually I sought in google, I got the answer and source code, but
still don't understand why.
;)
【在 c****t 的大作中提到】
: a very typical problem using dynamic programming. Search "coin changing"
: "dynamic programing" in google.
r*d
4 楼
设f1为只能用1 cent 的换法
f1(a)=1 for all a>=0;
设f2为可以用5 cent, 1 cent 的换法
f2(a)=f1(a)+f1(a-5)+f1(a-10)+...=sum( f1(a-i*5)) for all i,i>=0; i*5<=a
设f3为可用10,5,1,cent 的换法数
f3=f2(a)+f2(a-10)+...=sum (f2(a-i*10)) 0<=i<=i/10;
...
【在 c****d 的大作中提到】
: 给你 x cents ， 让你换成50, 25, 10, 5, 1 cent, 问有多少种换法？
: 用dynamic programming 解决。我想了很久， 不知道怎么做。请大虾指教
: ，并希望解释详细一些。我主要是对于分解问题想不清。谢谢
f1(a)=1 for all a>=0;
设f2为可以用5 cent, 1 cent 的换法
f2(a)=f1(a)+f1(a-5)+f1(a-10)+...=sum( f1(a-i*5)) for all i,i>=0; i*5<=a
设f3为可用10,5,1,cent 的换法数
f3=f2(a)+f2(a-10)+...=sum (f2(a-i*10)) 0<=i<=i/10;
...
【在 c****d 的大作中提到】
: 给你 x cents ， 让你换成50, 25, 10, 5, 1 cent, 问有多少种换法？
: 用dynamic programming 解决。我想了很久， 不知道怎么做。请大虾指教
: ，并希望解释详细一些。我主要是对于分解问题想不清。谢谢
相关阅读
人们说的 Binary Code 指的是什么？Why I think the paper is junk, but it still gets good simulation result?有没有准备回国参加ICCV的同仁, 签证会不会是个问题呢 (转载)问一个Markov Chain / Queue的问题job-oriented datamining training websitesQuestion about java appletPPC 和 Windows CE 是什么关系？independent set in cubic planar graphfrom power spectra to original signal有没有什么网站上可以查到老师需求学生的信息请教一个专业方向的问题A question when open a .chm file编程初学者!软工和生物计算那个更有前途啊：）求救：google map 旁边的zoom 条没有显示About the conference papers请教一个gnuplot问题问一下non-threshold secret sharing (转载)关于embedded systems招进来的博士生能有一半拿到博士就不错了