最少硬币问题

最少硬币问 3-4 最少硬币问题 ,问题描述: 设有n种不同面值的硬币，各硬币的面值存于数组T,1:n,中。现要用这些面值的硬 币来找钱。可以使用的各种面值的硬币个数存于数组Coins,1:n,中。 对任意钱数0?m?20001，设计一个用最少硬币找钱m的方法。 ,编程任务: 对于给定的1?n?10，硬币面值数组T和可以使用的各种面值的硬币个数数组Coins， 以及钱数m，0?m?20001，编程计算找钱m的最少硬币数。 ,数据输入: 由文件coins*.in提供输入数据,文件的第一行中只有1个整数给出的值,第2行起每行n2个数，分别是T[j]和Coins[j]。最后1行是要找的钱数m。 ,结果输出: 程序运行结束时,将计算得出的最少硬币数输出到文件coins*.out中。问题无解时输出-1。 输入文件示例 输出文件示例 coins0.in coins0.out 3 5 1 3 2 3 5 3 18 #include void Swap(long& a,long& b); void main() { long i=0,kind=0,k=0,j=0; ifstream inf("input.txt"); ofstream outf("output.txt"); //读数 inf>>kind; long* t; t=new long[kind]; long* coins; coins=new long[kind]; long* c; c=new long[kind]; for (i=0;i>t[i]>>coins[i]; long total=0,mincount=99999999,ccount=0; inf>>total; //计算 for (i=0;it[j]) { Swap(t[i],t[j]); Swap(coins[i],coins[j]); } } long sum=0; for (i=0;i0)&&(sum>=total)) for (i=kind-1;i>=0;i--) { Swap(t[i],t[kind-1]); Swap(coins[i],coins[kind-1]); if (t[kind-1]>0) { c[kind-1]=temptotal/t[kind-1]; if (c[kind-1]>=coins[kind-1]) c[kind-1]=coins[kind-1]; long tempcount=0; while((c[kind-1]>0)&&(c[kind-1]<=mincount)) { tempcount=c[kind-1]; temptotal=temptotal-t[kind-1]*c[kind-1]; for (j=kind-2;j>=0;j--) if ((temptotal>0)&&(t[j]>0)) { c[j]=temptotal/t[j]; if (c[j]>=coins[j]) c[j]=coins[j]; temptotal=temptotal-t[j]*c[j]; tempcount=tempcount+c[j]; } if ((tempcount>0)&&(tempcount