I AM A DUMMY, PLEASE MAKE IT SIMPLE- Thanx

You have an (arbitrary) set of coins C which have integer values. The only restrictions on C are:

a) All the coins have positive integer values

b) C must contain the coin of value 1

The problem to be solved is to specify the minimum number of coins which can be used to make up a given amount of change.

For example suppose that C = {1, 3, 7, 10} and you are asked to make up 25. You can do this in various ways:

10 + 10 + 3 + 1 + 1

10 + 10 + 1 + 1 + 1 + 1 + 1

10 + 7 + 7 + 1

7 + 7 + 7 + 3 + 1

…….and so on…….

As it turns out the solution 10+7+7+1 is optimal in this case.

I need to build two different solutions to the giving change problem:

•simple greedy algorithm (always take the largest coin available)

•stochastic search (take coins at random)

ANY IDEA HOW TO START.