Optimality of a Greedy Algorithm

Question

If you designed a greedy algorithm to obtain an optimal solution and the algorithm can produce different combinations of values but still, any of theses combination is an optimal solution. How you prove it is optimality?

For example you have a set of numbers $\mathcal{M}=\{1,2,3,4\}$ and you want to design an algorithm to obtain the minimum number of integers required to obtain a sum 5. In this case, $1,4$ or $2,3$ can produce 5 and both are optimal solutions as the minimum number required is two.

How to prove the optimality of the algorithm ?

I tried by contradiction an assume that there is an optimal solution $P^*$ and my algorithm doesnot produce an optimal solution $P$ so $P \neq P^*$. but I donot know how to continue the argument.

Answer 1

This is the change making problem. For some sets of denominations (e.g. powers of some base $b$, the US coins, or almost all coin systems in the world) the greedy algorithm gives the minimal number of coins. The general case is NP-complete, a practical solution requires dynamic programming (see the liked Wikipedia article). There is a polynomial time algorithm to check if a given set of denominations makes the greedy algorithm optimal or not, see Pearson (1994) "A polynomial-time algorithm for the change-making problem", doi 10.1.1.57.3243.

Answer 2

If a greedy algorithm is not always optimal then a counterexample is sufficient proof of this.

In this case, take $\mathcal{M} = \{1,2,4,5,6\}$. Then for a sum of $9$ the greedy algorithm produces $6+2+1$ but this is not optimal because $5+4$ has fewer summands.

Answer 3

Greedy algorithm usually involes a sequence of choices and once a choice is made we can't undo it in the next step. So it is important that they(greedy algorithm) never made a mistake. A local optimum solution means best possible solution.

Let set $S$ be an optimal solution to some problem and our greedy algorithm gives a set $P$. If both $P$ and $S$ are same then are done. Assume that both $P$ and $S$ are different,in this case greedy algorithm will have pick an element in the intermediate step(local solution) which is less optimal which resulted $P$ rather than optimal set $S$. But according to the greedy algorithm we always choose an local optimum solution. Hence the argument is proved by proof by contradiction.