0
$\begingroup$

Given a set of coin denomination (1,5,10) the problem is to find minimum number of coins required to get a certain amount. The greedy algorithm is to pick the largest possible denomination. I am unable to proof the correctness of this algorithm with denominations (1,5,10), How should I prove its correctness?

On the other hand if the denomination where (1,3,4,5,10) I am able to prove that for this set of denomination the greedy algorithm won't work by giving an example

For 7 greedy algorithm will pick (5,1,1)

The optimal solution is (3,4)

Is giving an example sufficient to prove that this algorithm with the set of denominations (1,3,4,5,10) doesn't work?

$\endgroup$

1 Answer 1

1
$\begingroup$

In the set {1,5,10}, every element is a factor of every larger element, which means that the algorithm described will work.

The same is not true of the set {1,3,4,5,10}.

And yes, your counterexample is sufficient to prove that the algorithm does not work in the general case for the denominations {1,3,4,5,10}.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .