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++编译器分别提交都返回未知错误呢大哥们看这有啥问题

[此贴子已经被作者于2007-9-18 10:36:28编辑过]

seems to be a dynamic programming problem.

我是先把钱的面额从小到大排序,然后在分配的时候先找面额大的,分配后m剩余的部分依次用面额小一点的硬币分配,这样按理说应该是求出的最小硬币数了吧,怎么它就是不认呢

改成这样提交又超时，原来还要支持连续输入第一次搞不懂规矩
[CODE]#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;
while(scanf("%d",&n))
{
if(n<=0)break;
i=0;
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;
}[/CODE]

[此贴子已经被作者于2007-9-18 12:55:19编辑过]