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?
Best Answer
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}.