Proof of the correctness of greedy strategies for solving specific coin problems

Problem description

Suppose the currency of the change system is {1,.. .}, p>1, and the number of each coin meets the requirements, design an algorithm with the lowest time complexity in the worst case, so that for any money y, the algorithm can get the least number of change.

Greedy strategy

Arrange your change from the largest amount to the smallest, using each amount as much as possible, starting with the largest amount. If the change is smaller than that amount, consider using the next coin.

prove

For the currency system {1,.. .}, p>1, in terms of money y, suppose that the solutions obtained by greedy selection are arranged as {... .}, i.e., y =++… +; And the optimal solution is {... .}, y =++… +.

The two are proved to be the same by contradiction. If the greedy solution is different from the optimal solution, it can be assumed that the different position k appears for the first time when the change is withdrawn from the largest to the smallest in terms of currency value, i.e=(kiN), because of the nature of greedy strategies, there must be>. Meanwhile, for 0iK for sureP, because ifP, you can use a pⁱ⁺¹Student: Currency instead of p sheet PⁱThe value of money, the number of change decreases, and the optimality of the optimal solution contradiction.

Because y =++… +=++… +, the first occurrence of a different position is k,=(kiN), it is++… +=++… +. According to the zeroiK,P,P – 1, thereby++… +b_k-1p^k-1+++… +p^k-1++– 1++… +To sum up, greedy solution must be the optimal solution.