作者allen65535 (來來回回的人)
看板Inference
標題Re: [問題]找錢問題 不知道能不能在這邊問～
時間Wed Apr 18 01:59:19 2007
※ 引述《weiluner (遊戲人間^^y)》之銘言：
: 如果今天我們的幣值是25元、20元、10元、5元、1元
: 利用以上方法 40元就不適用了
: 最後 因為這個是一個資工作業
: 所以老師要我們寫一個程式解決第二種幣值要找出最小銅板數的問題
我想最後這兩句才是重點，這本來就是一個找不太出邏輯的問題。
所以讓程式去跑才是最實在的。
在這裡1元的角色是比較特別的，剩下找不出來的錢，再用1元補就好。
我想到的方法是，用4個迴圈分別對應25元、20元、10元、5元，
迴圈要跑的東西是該種幣值從最少可以用幾個到最多可以用幾個，
例如25元就是從0到1。
for (i=...)
for (j=...)
for (k=...)
for (l=...)
用一個變數儲存你用了幾個硬幣，
找到比較小的解的時候就把他覆蓋過去。
當然還要排除一些不可能的狀況，
例如25元用2個和20元用2個的時候，就超過40元了
碰到這種狀況的時候就讓程式跳過就好。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.115.225.126
1F：推 ddavid:這是一個dynamic programming問題，用你的方法效率會較差 04/18 02:01
2F：→ ddavid:實際用來解決的方法在第一篇teves的推文已有提到 04/18 02:02
3F：推 ddavid:另外這並不是一個找不出邏輯的題目 04/18 02:04
4F：→ ddavid:我沒記錯的話這個題目是已經被研究過的題目了。 04/18 02:05
5F：推 allen65535:效率差我也知道,不過作業本來就是每個人都要不一樣啊XD 04/18 02:13
6F：→ allen65535:如果有限定要用dynamic programming老師應該會講吧 04/18 02:14
7F：推 ddavid:有最佳做法的題目，當你想到了最好那個方法， 04/18 02:15
8F：→ ddavid:那跟別人一樣是正常的啊XD 04/18 02:15