Prove the Correctness of Greedy Algorithms

Restricted search space

A greedy algorithm restricts the search space by selecting the most profitable piece of a solution at each step. For example, the $LargestConcatenate$ algorithm only considers concatenations starting from the largest digit instead of considering all possible concatenations. Instead of all possible ways of changing money, the $Change$ algorithm considers only the ones that include a coin with the largest denomination (that does not exceed $money$).

An arbitrary optimal solution

What we need to prove is that the restricted search space still contains at least one optimal solution. This is usually done as follows:

• Consider an arbitrary optimal solution.
• If it belongs to the restricted search space, then we’re done.
• If it does not belong to the restricted search space, tweak it so that it’s still optimum and belongs to the restricted search space.

Proving the correctness of $LargestConcatenate$