题目我变了 更有意思 在我原来的基础上加了一个问题 题目在31楼

凑钱

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名
多谢大家的帮忙啊
----------------解决方案--------------------------------------------------------
斑竹所说的贪心算法，应该就是老想到所有可取的里面挑大的
比如给我10元钱，所有面值的任我挑，那我挑一张10元面值的，而不拿两张5元的或是其他的选择。
如果说得不对请见谅
----------------解决方案--------------------------------------------------------
说的对极了.呵呵
就是这个意思.能睡着就不站着.
----------------解决方案--------------------------------------------------------

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

----------------解决方案--------------------------------------------------------
不知道如何下手
----------------解决方案--------------------------------------------------------
贪心一般是先做排序。然后优先选择
----------------解决方案--------------------------------------------------------