[求助]NK1132 最少硬币问题
Link: http://acm.nankai.edu.cn/p1132.html
问题:
设有n 种不同面值的硬币,各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins[1:n]中。
对任意钱数0≤m≤20001,设计一个用最少硬币找钱m的方法。
编程任务:
对于给定的1≤n≤10,硬币面值数组T和可以使用的各种面值的硬币个数数组Coins,以及钱数m,0≤m≤20001,编程计算找钱m的最少硬币数。
Input
输入包括多组测试数据,每组输入的第一行中只有1 个整数给出n的值,第2 行起每
行2 个数,分别是T[j]和Coins[j]。每组输入最后1 行是要找的钱数m。
Output
对于每组输入数据,输出一行,即计算出最少硬币数。问题无解时输出-1。
我的方法:
#include <stdio.h>
int main()
{
int T[11]={0},Coins[11]={0},m=0,n=0,i=0,sum=0,t=0;
int a=0,b=0,temp=0,j=0;
scanf("%d",&n);
do
{
i++;
scanf("%d%d",&T[i],&Coins[i]);
}while(i<n);
scanf("%d",&m);
b=m;
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
{
if(T[j]<T[i])
{
temp=T[j];
T[j]=T[i];
T[i]=temp;
temp=Coins[j];
Coins[j]=Coins[i];
Coins[i]=temp;
}
}
for(i=n;i>=1;i--)
{ if(m>=T[i])
{
t=(m/T[i])>Coins[i]?Coins[i]:m/T[i];
sum=sum+t;
a=a+t*T[i];
m=m-t*T[i];
}
else continue;
}
if(a==b)
printf("%d",sum);
else
printf("%d",-1);
return 0;
}
我测试可以呀,为什么提交几次,并选择了GNUC,GNUC++编译器分别提交都返回未知错误呢大哥们看这有啥问题
int main()
{
int T[11]={0},Coins[11]={0},m=0,n=0,i=0,sum=0,t=0;
int a=0,b=0,temp=0,j=0;
scanf("%d",&n);
do
{
i++;
scanf("%d%d",&T[i],&Coins[i]);
}while(i<n);
scanf("%d",&m);
b=m;
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
{
if(T[j]<T[i])
{
temp=T[j];
T[j]=T[i];
T[i]=temp;
temp=Coins[j];
Coins[j]=Coins[i];
Coins[i]=temp;
}
}
for(i=n;i>=1;i--)
{ if(m>=T[i])
{
t=(m/T[i])>Coins[i]?Coins[i]:m/T[i];
sum=sum+t;
a=a+t*T[i];
m=m-t*T[i];
}
else continue;
}
if(a==b)
printf("%d",sum);
else
printf("%d",-1);
return 0;
}
[此贴子已经被作者于2007-9-18 10:36:28编辑过]