當前有面值分別為2角5分,1角,5分,1分的硬幣,請給出找n分錢的最佳方案(要求找出的硬幣數目最少)
問題分析:
根據常識,我們到店裏買東西找錢時,老板總是先給我們最大面值的,要是不夠再找面值小壹點的,直到找滿為止。如果老板都給妳找分數的或者幾角的,那妳肯定不幹,另外,他也可能沒有那麽多零碎的錢給妳找。其實這就是壹個典型的貪心選擇問題。
問題的算法設計與實現:
先舉個例子,假如老板要找給我99分錢,他有上面的面值分別為25,10,5,1的硬幣數,為了找給我最少的硬幣數,那麽他是不是該這樣找呢,先看看該找多少個25分的, 99/25=3,好像是3個,要是4個的話,我們還得再給老板壹個1分的,我不幹,那麽老板只能給我3個25分,由於還少給我24,所以還得給我2個10分的和4個1分。
具體實現
//找零錢算法
//By falcon
//輸入:數組m,依次存放從大到小排列的面值數,n為需要找的錢數,單位全部為分
//輸出:數組num,對照數組m中的面值存放不同面值的硬幣的個數,即找錢方案