問題描述：給出幾種面值的硬幣，要求用這幾種硬幣找零出所給零錢數，用的硬幣數要最少。

過去我們用過貪心法解決此類問題，包括本人在百度面試時，也是用的貪心法（面試官對這個解答不滿意），貪心法只適用于硬幣特殊的情況下（1,3,5），如果現在硬幣的面值為10,7,3,1，要求給出21的找零方案，那么貪心會給出10,7,3,1的方案，而不是3個7塊的最佳方案。

那么動態規劃又該如何解決，動態規劃在于在解決問題的途中用到之前的得到的答案。

思考：求n的找零方案時，可將問題分解為1-（n-1）的找零方案中加上一個已知面值的硬幣，求其最小值便可。

代碼如下：

#include<iostream> using namespace std;//三個參數依次是硬幣面值數組，硬幣種類，給出的零錢 void getMin(int *values,int valueKinds,int money){int *coinUsed = new int[money+1]();int *coinUsedNum = new int[money+1]();//（之前寫的代碼無法得出在無法找零情況下的正確答案，用這個數組不僅可以記錄給出的硬幣，還可以得出是否能找開的情況） coinUsed[0] = 0;for(int cent=1;cent<=money;cent++){//每個零錢找零的最大值便是最小面值組成的個數 int minCent = cent;int moneyUsed = 0;for(int kind=0;kind<valueKinds;kind++){if(values[kind]<=cent){//所查找找零最小數為已知的零錢找零數 + 一個已有面值，便是最少硬幣方案 int temp = coinUsed[cent - values[kind]] + 1;//此處應該做一個判斷，即是否找得開，找不開便不必更新最小值 if(temp <= minCent && (cent == values[kind] || coinUsedNum[cent - values[kind]] != 0)){minCent = temp;moneyUsed = values[kind];}}}coinUsed[cent] = minCent;coinUsedNum[cent] = moneyUsed;}if(coinUsedNum[money] == 0){printf("面值為%d的零錢找不開！", money);} else {printf("面值為%d的最少找零數為%d,", money,coinUsed[money]);printf("找零面值分別為：");while(money>0){printf(" %d",coinUsedNum[money]);money -= coinUsedNum[money];}} }int main(){int a[5] = {2,5,10,21,25};int money = 24;getMin(a,5,money); }

?

轉載于:https://www.cnblogs.com/tz346125264/p/7341143.html

總結

以上是生活随笔為你收集整理的硬币找零问题，动态规划基础，百度面试题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。