當前位置:編程學習大全網 - 編程軟體 - 找零錢問題的貪心算法

找零錢問題的貪心算法

問題描述:

當前有面值分別為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中的面值存放不同面值的硬幣的個數,即找錢方案

  • 上一篇:學習編程的幾點註意事項
  • 下一篇:什麽是SAMA圖?及相關圖例介紹
  • copyright 2024編程學習大全網