找零钱 解题报告

描述：

PoorBessiehastakenajobintheconveniencestorelocatedjustovertheborderinSlobbovia.SlobboviansusedifferentcoinagesthantheUSA;theircoinvalueschangeday-by-day!
HelpBessiemakeoptimalchangeforSlobbovianshoppers.YouwillneedtocreateC(1<=C<=1000)centsofchangeusingN(1<=N<=10)coinsofvariousvalues.Alltestcaseswillbesolvableusingthesuppliedcoins.
If5coinsofvalues50,25,10,5,and1wereavailable,Bessiewouldmakeoptimumchange(minimalcoins)of93centsbyusing1x50,1x25,1x10,1x5,and3x1coins(atotalof7coins).
Howhardcoulditbe?Thefinaltwotestcaseswillbechallenging.

输入：

Line1:Twospace-separateintegers:CandN
Lines2..N+1:Eachlinecontainsasingleuniqueintegerthatisacoinvaluethatcanbeusedtocreatechange

输出：

Line1:AsingleintegerthatistheminimumnumberofcoinstocreateCcents

输入样例：

935
25
50
10
1
5
输出样例：7



解题思路：先想到用贪心法，可以从大的面额开始算，直到超出，然后换成小的面额去求，直到求出一个N，但后来总觉得有个地方可能会做不到，没那么容易贪的，如果面额没有1的时候，是不是可能出现不能刚好的情况，这个时候就得反过来让大的面额进行减少的处理，有点小麻烦。就想用另一种方法，动态规划，比如既然要求面额为93的最优解，就得求出92、91、90一直到1的最优解，把问题一直小化处理

例如：面值为50、25、1、10、5求93的最优解

要求93得先求43、68、92、83、88的最优解+1，就这样一直求下去

时间复杂度：O（m*n）；

代码如下：

#include<iostream>

usingnamespacestd;



intmain()

{

intn,m;

inta[500]={0};

intb[10000]={0};

cout<<"请输入硬币面值的个数：";

cin>>n;

cout<<"请输入各个硬币的面值:";

for(inti=1;i<=n;i++)

cin>>a[i];

cout<<"请输入要找的钱:";

cin>>m;

voidcoin(intn,intm,inta[],intb[]);

coin(n,m,a,b);

cout<<"最优解为："<<b[m]<<endl;

return0;

}



voidcoin(intn,intm,inta[],intb[])

{

b[0]=0;

for(inti=1;i<=m;i++)

{

intmin=m;

for(intj=1;j<=n;j++)

{

if(i>=a[j]&&b[i-a[j]]<min)

min=b[i-a[j]];

}

b[i]=min+1;

}

}