找零问题贪心算法实现
一、实验描述
当前有面值分别为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分。
具体实现：
<<endl;
outputFile<<setw(4)<<"面值"<<setw(7)<<"个数"<<endl;
int sum=0;
for (int i=1;i<=number;i++)
{ inputFile>>T[i];
inputFile>>Coins[i];
outputFile<<setw(3)<<T[i]<<setw(3)<<" "<<setw(3)<<Coins[i]<<endl;
sum+=T[i]*Coins[i];
}
inputFile>>TotalMoney;
outputFile<<"需要找回的总钱数为: "<<TotalMoney<<endl;
if (T!=NULL && Coins!=NULL)
{ if (sum>=TotalMoney)return true;
else outputFile<<"所有硬币的总钱数是"<<sum<<" 小于需要找回的总钱数"<<TotalMoney<<endl;
return false;
}
return false;
}
int LeastCoins::changeMoney(int i,int j)
{ if (i>1)
{ if (j<T[i]) // 要找的钱数小于该硬币的面值
{m[i-1][j]=changeMoney(i-1,j);m[i][j]=m[i-1][j]; return m[i][j]; }
else
{ int X=j/T[i];
X=(X<Coins[i] X : Coins[i]) ;
int T1=changeMoney(i-1,j-X*T[i]);
int T2=changeMoney(i-1,j-(X-1)*T[i]);
m[i-1][j-X*T[i]]=T1;
m[i-1][j-(X-1)*T[i]]=T2;
if ((T1+X)>(T2+X-1)) m[i][j]=T2+X-1;
else m[i][j]=T1+X;
return m[i][j];
}
}
else if(i==1)// 此时 i==1
{ if ((j%T[1])==0 && (j/T[1]<=Coins[1])){ m[1][j]=j/T[1]; return m[1][j]; } else return 1000000;
}
else return 1000000;
}
void LeastCoins::output()
{ if (m[number][TotalMoney]<1000000) // 判断是否有解
{ outputFile<<"需要最少的硬币个数是: "<<m[number][TotalMoney]<<endl;
outputFile<<setw(4)<<"面值"<<setw(7)<<"个数"<<endl;traceback();
}
else outputFile<<"无解"<<endl;
}
void LeastCoins::traceback()
{
int j=TotalMoney;
for (int i=number;i>=2;i--)
{
int X=j/T[i]; // 最多需要面值为 T[i] 的硬币的个数
X=(X<Coins[i] X : Coins[i]) ; // 取 X 和 Coins[i]的较小值
int T1=m[i-1][j-X*T[i]]+X;
int T2=m[i-1][j-(X-1)*T[i]]+X-1;
if (T1<T2)
{ outputFile<<setw(3)<<T[i]<<setw(3)<<" "<<setw(3)<<X<<endl; j-=X*T[i]; } else { outputFile<<setw(3)<<T[i]<<setw(3)<<" "<<setw(3)<<(X-1)<<endl;
j-=(X-1)*T[i]; }
}
outputFile<<setw(3)<<T[i]<<setw(3)<<" "<<setw(3)<<(j/T[1])<<endl;
}
int main()
{ LeastCoins LC;
();
return 0;
}
三、运行结果
图1 运行结果
四、实验总结
对贪心算法不是特别熟悉，以至于在编写程序时遇到好多错误，好在差不多都改正了，此程序尚有不足之处，希望在以后的深入学习后能编写个更好的程序。