一个网站是如何知道是谁来访问,中公it培训机构怎么样,wordpress 更改icon,昆明市做网站公司问题描述#xff1a;给出几种面值的硬币#xff0c;要求用这几种硬币找零出所给零钱数#xff0c;用的硬币数要最少。 过去我们用过贪心法解决此类问题#xff0c;包括本人在百度面试时#xff0c;也是用的贪心法#xff08;面试官对这个解答不满意#xff09;#xff… 问题描述给出几种面值的硬币要求用这几种硬币找零出所给零钱数用的硬币数要最少。 过去我们用过贪心法解决此类问题包括本人在百度面试时也是用的贪心法面试官对这个解答不满意贪心法只适用于硬币特殊的情况下1,3,5如果现在硬币的面值为10,7,3,1要求给出21的找零方案那么贪心会给出10,7,3,1的方案而不是3个7块的最佳方案。 那么动态规划又该如何解决动态规划在于在解决问题的途中用到之前的得到的答案。 思考求n的找零方案时可将问题分解为1-n-1的找零方案中加上一个已知面值的硬币求其最小值便可。 代码如下 #includeiostream
using namespace std;//三个参数依次是硬币面值数组硬币种类给出的零钱
void getMin(int *values,int valueKinds,int money){int *coinUsed new int[money1]();int *coinUsedNum new int[money1]();//之前写的代码无法得出在无法找零情况下的正确答案用这个数组不仅可以记录给出的硬币还可以得出是否能找开的情况 coinUsed[0] 0;for(int cent1;centmoney;cent){//每个零钱找零的最大值便是最小面值组成的个数 int minCent cent;int moneyUsed 0;for(int kind0;kindvalueKinds;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(money0){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
