請教有關動態規划的找錢問題 -开发者知识库

請教有關動態規划的找錢問題 -开发者知识库,第1张

這是一個古老而又經典的問題。用給定的幾種錢幣湊成某個錢數,一般而言有多種方式。例如:給定了6種錢幣面值為2、5、10、20、50、100,用來湊15元,可以用5個2元、1個5元,或者3個5元,或者1個5元、1個10元,等等。顯然,最少需要2個錢幣才能湊成15元。
你的任務就是,給定若干個互不相同的錢幣面值,編程計算,最少需要多少個錢幣才能湊成某個給出的錢數。

【要求】
【數據輸入】輸入可以有多個測試用例。每個測試用例的第一行是待湊的錢數值M(1<=M<=2000,整數),接着的一行中,第一個整數K(1<=K<=10)表示幣種個數,隨后是K個互不相同的錢幣面值Ki(1<=Ki<=1000)。輸入M=0時結束。

【數據輸出】每個測試用例輸出一行,即湊成錢數值M最少需要的錢幣個數。如果湊錢失敗,輸出“Impossible”。你可以假設,每種待湊錢幣的數量是無限多的。

請大家首先考慮用10元,7元,1元找開14元的問題,謝謝了,本人菜鳥,最好給出代碼的同時有注釋,並先用文字解釋大體思路,謝謝了!!

2 个解决方案

#1


請教有關動態規划的找錢問題 -开发者知识库,第2张可以參考一下這本書王曉東的《計算機算法設計與分析答案》和《算法與數據結構學習指導與習題解析》這里面有具體的實現過程
這題是一題動態規划,設有n種不同面值的硬幣,各硬幣的面值存於數組T[1……n]中

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复