| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2090 人关注过本帖
标题:[求助]NK1132 最少硬币问题
只看楼主 加入收藏
weishj
Rank: 1
等 级:新手上路
威 望:2
帖 子:141
专家分:0
注 册:2007-4-22
收藏
 问题点数:0 回复次数:3 
[求助]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++编译器分别提交都返回未知错误呢大哥们看这有啥问题

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

搜索更多相关主题的帖子: 硬币 
2007-09-18 10:30
HJin
Rank: 6Rank: 6
等 级:贵宾
威 望:27
帖 子:401
专家分:0
注 册:2007-6-9
收藏
得分:0 

seems to be a dynamic programming problem.


I am working on a system which has no Chinese input. Please don\'t blame me for typing English.
2007-09-18 10:58
weishj
Rank: 1
等 级:新手上路
威 望:2
帖 子:141
专家分:0
注 册:2007-4-22
收藏
得分:0 
我是先把钱的面额从小到大排序,然后在分配的时候先找面额大的,分配后m剩余的部分依次用面额小一点的硬币分配,这样按理说应该是求出的最小硬币数了吧,怎么它就是不认呢

If you shed tears when you miss the sun, you also miss the stars.
2007-09-18 11:01
weishj
Rank: 1
等 级:新手上路
威 望:2
帖 子:141
专家分:0
注 册:2007-4-22
收藏
得分:0 
改成这样提交又超时,原来还要支持连续输入第一次搞不懂规矩
[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编辑过]


If you shed tears when you miss the sun, you also miss the stars.
2007-09-18 11:31
快速回复:[求助]NK1132 最少硬币问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.028038 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved