凑钱

Time Limit:1000MS Memory Limit:65536K
Total Submit:1 Accepted:0

Description

某国的货币只有n种，它们的面值分别是value1,value2,...,valuen.现在我要买一件商品，它值cost元.我只能用这n种货币付款,并且每种货币我有任意枚。n种货币凑齐cost元吗？如果能够凑齐的话，最少需要多少枚货币呢？

Input

每组测试数据占2行。
第一行有2个正整数n，cost(0＜n＜1000，0＜cost＜=10000)。
第二行有n个整数，表示value1,value2,...,valuen(0＜valuei＜=10000)。

Output

每组测试数据输出它的结果，占一行。如果能够凑好，输出需要最少的货币数;否则输入"bad".

Sample Input

4 10
1 2 5 10
4 13
2 4 6 8

Sample Output

1
bad

[此贴子已经被作者于2007-11-2 16:00:12编辑过]

没有接触过谈心法 指教

报告斑竹 我们队再昨天的比赛中的17名
多谢大家的帮忙啊

我昨天也是这样排序 然后挑大的 但是 比如
对于输入的
1 2 5 10
13元 结果 3
17元 结果 3

不知道如何下手

你的对于小数还可以 大了就不行了 超时
#include <iostream>
using namespace std;
int main()
{ int n,m,i,j;
while(scanf("%d%d",&n,&m)!=EOF)
{
int a[1000]={0},b[200000]={0};
for (i=0;i<n;i++)
scanf("%d",&a[i]);
for (i=0;i<n;i++)
b[a[i]]=1;
for (i=1;i<=m;i++)
for (j=0;j<n;j++)
{
if (i-a[j]>0)
if (b[i]==0)
{
if (b[i-a[j]]!=0)
b[i]=b[i-a[j]]+1;
}
else
{
if (b[i-a[j]]!=0&&b[i-a[j]]+1<b[i])
b[i]=b[i-a[j]]+1;
}
}
if (b[m]==0) printf("bad\n");
else printf("%d\n",b[m]);
}
return 0;
}

我的搜索+回溯 请教各位怎么改
#include <stdio.h>
#include <algorithm>
using namespace std ;
struct Coin
{
int value ;
int num ;
}T[11] ;
int comp(Coin a ,Coin b )
{
return a.value <= b.value ;
}
int main()
{
int i ;
int n ;
int m ,sum ;
while(scanf("%d%d",&n,&m ) != EOF)
{
for( i = 0 ; i < n ; i ++ )
{
scanf("%d",&T[i].value);
}
sort(T,T+n ,comp );
sum = 0 ;
int k = -1 ;
for( i = n-1 ; i >=0 ; i-- )
{
if( T[i].value <= m )
{
k = i ;
break;
}
}
while(k>0)
{
sum ++ ;
m = m - T[k].value ;
if(m<T[k-1].value )
m=m + T[k].value;
k=k-1;
printf("%d\n",m);
}
if(m == 0)
printf("%d\n",sum ) ;
else
printf("bad\n");
}
return 0 ;
}

大哥 这组测试用例通不过
4 18
3 4 7 10
3
4 28
10 9 4 3
4


4 18
10 9 4 3
3
最后应该是
9 9 结果是2 而不是3
请指教

还是不行
输入
13 4的时候
2 4 6 8
结果是2

你先改成循环输入
切先输入
4 18
10 9 4 3
再
4 13
2 4 6 8