#include<iostream> using namespace std;//coinNum[i]當前錢為i時需要的最少硬幣數 void FindMin(int money,int *coin, int n) {int *coinNum = new int[money+1]();//存儲1...money找零最少需要的硬幣的個數int *coinValue = new int[money+1]();//最后加入的硬幣，方便后面輸出是哪幾個硬幣coinNum [0] = 0;for(int i = 1;i <= money;i++){int minNum = i;//i面值錢，需要最少硬幣個數,全部為1時，對應的最大個數int usedMoney = 0;//這次找零，在原來的基礎上需要的硬幣for(int j = 0; j < n;j++) //遍歷可用的零錢{if( i >= coin[j])//找零的錢大于這個硬幣的面值{if(coinNum[i-coin[j]] + 1 <= minNum && (i == coin[j] || coinValue[i-coin[j]] != 0))//所需硬幣個數減少了{minNum = coinNum[i-coin[j]] + 1; usedMoney = coin[j]; }}}coinNum[i] = minNum;coinValue[i] = usedMoney; //當錢為i時可以用的錢}//輸出結果if(coinValue[money] == 0)cout<<"找不開零錢"<<endl;else{cout<<"需要最少硬幣個數為："<<coinNum[money]<<endl;cout<<"硬幣分別為:";while(money>0){cout << coinValue[money] << ",";money -= coinValue[money];}}delete []coinNum;delete []coinValue; }int main() {int Money = 18;int coin[] = {1,2,5,9,10};FindMin(Money,coin,5);return 0; }

看上圖，總共15元，有{1,5,11}的面值，類似一個地推過程。coinValue[money] == 0表示找不開，如果能找開肯定有值，因為上面usedMoney進行賦值了。

?

?

地址代碼：https://blog.csdn.net/kangroger/article/details/36036101#

視頻地址：https://haokan.baidu.com/v?vid=2742116767553288532&pd=bjh&fr=bjhauthor&type=video

?

?

總結

以上是生活随笔為你收集整理的动态规划--用最少的硬币类别找零钱的全部內容，希望文章能夠幫你解決所遇到的問題。

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