本站遷移

因為我最近租用了網路空間以及網域,
故本站已遷移至新網站~
這邊的資訊已經正在進行搬移的工作~
希望各位可以到新網站去逛XD

New Website:
http://knightzone.org/

搜尋此網誌

2011年3月1日 星期二

[UVa]147:Dollars

這題是DP的找零錢問題。

有幾種組合的算法,
由於可能會有重覆算到的關係,
所以要先加入最小的零錢(此題是5c)進去,
看看各個值(小於等於300.00)假設最後一枚硬幣為此零錢能用幾種方法(其實是dp[該值-加入的零錢價值]種)找出來,
接著再把次小的零錢(此題是10c)放進去,
看看各個值(小於等於300.00)假設最後一枚硬幣為此零錢能用幾種方法(其實是dp[該值-加入的零錢價值]種)找出來,
這樣以此類推到最大的零錢,
這樣我在算最後一個零錢是10c的組合的時候,
我只會找出5c跟10c的組合,
不會找出配上20c啦...50c啦...或是1元之類的組合。
等到我在算最後一個零錢是20c的組合的時候,
我只會找出5c跟10c跟20c的組合,
不會找出配上50c啦...或是1元之類的組合。
(如果看不懂以上內容,可以翻閱關於DP找零錢問題的教學文章。)

再來應該要建dp表,我們不可能用小數當索引值,
所以我們可以把該值乘上100在對應dp的那格為其答案,
但是浮點數乘法再配上轉成整數是避不開誤差的Orz...
因此請善用兩個整數來存值XD

[C](0.020)

0 意見:

張貼留言