作者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