作者weiluner (游戏人间^^y)
看板Inference
标题[问题]找钱问题 不知道能不能在这边问～
时间Tue Apr 17 00:07:58 2007
最近遇到一个问题 因为一直想不出要怎麽解决
爬文似乎也没有类似的问题 不知道PO在这会不会很奇怪
希望板上大大能给一些想法
店员有25元、10元、5元、1元的币值
要找77元给顾客，方法有很多种
其中一种找钱的方法是先把77除以25整数为3
余数2再除以10以及5整数皆为0
2除以1整数为2
如此一来 我们可以拿出3个25元硬币以及2个1元硬币给顾客
而且这也是铜板总数目最小的方法
我想问的是
如果要找出一种铜板总数目最小的方法
这种把要找钱的数目先从大的币值除
所得余数再由第二小的币值一直除下来的方法能够通用在所有的钱数吗
如果可以 要如何证明呢？
如果今天我们的币值是25元、20元、10元、5元、1元
利用以上方法 40元就不适用了
最小的硬币数是2个20元 而不是1个25元、1个10元以及1个5元
我想知道这两种币值有什麽差异
为什麽第一种币值就可以用这种方式 而第二种不行
最後 因为这个是一个资工作业
所以老师要我们写一个程式解决第二种币值要找出最小铜板数的问题
希望各位大大不吝指教
感恩~ <(_ _)>
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 163.25.118.149
1F：推 teves:对於你的第一个问题,你都举出反例了还用证明吗XD 04/17 00:34
2F：→ teves:至於你的作业,很明显是用dynamic programming 04/17 00:35
3F：→ teves:当你拿走任意一个硬币以後,等同於一个金额较少的相同问题 04/17 00:36
4F：→ teves:所以 数量(金额)=1+min(数量(金额-25),数量(金额-20),...) 04/17 00:37