Compare the greedy solution with any optimal solution. If the two solutions differ, then find the first x_i at which they differ. Next, it is shown how to make the x_i in the optimal solution equal to that in the greedy solution without any loss in total value. Repeated use of this transformation shows that the greedy solution is optimal.

This technique of proving solutions optimal is used often in this text. Hence, you should master it at this time.