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 proof that this algorithm with the set of denominations (1,3,4,5,10) doesn't work?


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}.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.