This article was translated from my Japanese blog.
2069 Greedy, Greedy
Problem
You are given n coins c1, …, cn. Determine if there are amounts that cannot be paid with exact change by the coins. Also, if every amount can be paid with exact change, determine if there is an amount of money that is not optimal by the greedy method, which means the greedy method cannot find the optimal solution for the coin exchange problem. (1 ≤ n ≤ 50, 0 < c1 < … < cn < 1000)
Solution
Since it can be easily proven by induction that “there is an amount that cannot be paid with exact change by given coins” ⇔ “there is an amount between 1, 2, …, cn that cannot be paid with exact change by given coins”, you can determine it by iterating over 1, …, cn in O(cn).
If you can pay every amount in exact change, you need to check whether there is an amount of money that you cannot find the optimal solution by the greedy method. However, you only have to check whether the greedy solution is consistent with the optimal solution for each amount between 1, …, 2cn by the following fact.
The minimum amount a for which a greedy solution is not optimal is up to 2cn. i.e., a ≤ 2cn.
Let’s define some notations for simplicity as follows: $$ \begin{align} a &:= \text{the minimum of all amounts for which the greedy solution is not optimal}, \\ opt(x) &:= \text{the optimal solution for }x, \\ grd(x) &:= \text{the greedy solution for }x. \end{align} $$ If we assume a > 2cn , opt(a) < grd(a) is true by definition.
Since cn < a − cn < a, $$ \begin{aligned} grd(a) &= grd(a - c_n) + 1 = opt(a - c_n) + 1. \end{aligned} $$
Also, since we know cn < a − cn < a − ci < a for all ci, and by the definition of opt, $$ \begin{aligned} opt(a) &= \min_{i = 1, \dots, n}\{opt(a - c_i) + 1\} \\ &=\min_{i = 1, \dots, n}\{grd(a - c_i) + 1\} \\ &=\min_{i = 1, \dots, n}\{grd(a - c_i - c_n) + 2\} \\ &=\min_{i = 1, \dots, n}\{opt(a - c_n - c_i) + 1\} + 1 \\ &= opt(a - c_n) + 1 \\ &= grd(a). \end{aligned} $$ This is a contradiction. Thus, a ≤ 2cn.
The greedy solution can be calculated in O(n) and the optimal solution can be precomputed with dynamic programming in O(n ⋅ 2cn). So, the total runtime complexity is O(ncn).