[問題] Casher's Algorithm 一問

[DRLai (蘇打)]

開發平台(Platform): (Ex: VC++, GCC, Linux, ...) 
GCC


額外使用到的函數庫(Library Used): (Ex: OpenGL, ...) 


問題(Question)：
http://www.csie.ntnu.edu.tw/~u91029/Greedy.html
最近在研究 casher's algorithm
(就是使用最少的銅板湊出所需要的金額)

很好奇上述的文章寫了一段
現實生活中，錢幣面額是經過精心設定的，可以安心使用 Cashier's Algorithm 。

不幸的消息是，並不是任意一種面額組合，都可以使用 Cashier's Algorithm 。要使用
 Cashier's Algorithm ，得先經過驗證才行：

一、各種價錢都能找，不會有找不出來的情況。
二、錢幣用量真的是最少的。

想到的演算法跟上述網址寫的一樣，但不知道為什麼網站上又要補充上述文字
是否是因為此演算法有考慮不周全的地方呢?



餵入的資料(Input)：


預期的正確結果(Expected Output)：


錯誤結果(Wrong Output)：


程式碼(Code)：(請善用置底文網頁, 記得排版) 


補充說明(Supplement)：


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 219.84.235.49
→ scwg:面額 $1, $3, $4, 湊 $6: greedy 會找到三個, 最佳只要兩個
→ DRLai:了解了..我少考慮~ Thanks!
→ scwg:其實網頁上說得也不太對, 1982 到 1990 年間英國同時有 25 和
→ scwg:20 pence 的硬幣. 這樣也不能 greedy (e.g. 40 pence)
→ scwg:現實生活中的硬幣設計其實沒有考慮過能不能 greedy 的問題
→ Schottky:現實生活中就算有推出某種面額, 大家也是會不爽用
→ Schottky:Ex: 我國的 $20 硬幣, $2000 鈔票...
→ diabloevagto:有20元硬幣？！
→ purincess:有喔 雙色的 跟以前的五十元顏色相反
→ purincess:http://zh.wikipedia.org/wiki/File:20-3zz.jpg
→ DRLai:有店家找過我20耶~ 不過我只看過一次
→ Schottky:有興趣可以到台灣銀行櫃檯換幾個來玩,兌幣櫃檯不用抽號碼
→ Schottky:我完全忘記還有 $200 紙鈔了
→ EdisonX:怎麼沒人提到 50 元 "紙鈔"..
推 lsc36:每一種面額必須是所有比他小的面額的倍數?
→ suhorng:好像是個充分條件而已XD
→ suhorng:我記得有個 O(n^3) 的算法判斷某組幣值是否可以用greedy