Maximal counterexample for a greedy approach with a non-canonical coin system

Question

Let $1 = c_1 < c_2 < \dots < c_n$ be an integer coin system. This coin system is not necessarily canonical (that is, a greedy algorithm will not necessarily yield the fewest number of coins for all change making combinations). However, when making change for a sufficiently large value $N \gg c_n$, one can start with a greedy approach, iteratively using the highest available denomination until we reach a value $N' = N - mc_n$ whose optimal solution does not use $c_n$. I would like to find an upper bound for $N'$.

Rigidly, my question is the following: What is the largest value of $N$ such that if $w_1, \dots, w_n$ are nonnegative integers that minimize $\sum_i w_i$ subject to the constraint $N = \sum_i c_i w_i$, then $w_n = 0$? Put into plain English, what is the largest value of $N$ for which one cannot use $c_n$ to obtain an optimal solution to the coin exchange problem? If such a value cannot be algorithmically determined, then what is a good upper bound for $N$?

I am aware of some results about where canonical counterexamples must exist if they do (e.g., [Cozen & Zaks] show that if a counterexample exists, then a minimal counterexample exists between $c_3 + 1$ and $c_{n-1} + c_n$), but I do not see any clear way of reducing my question to questions of this sort, and I am unfamiliar with the broader research done on this topic.

Answer 1

Here is a quick upper bound. If $N > (c_n-1)(c_1 + c_2 + \dots + c_{n-1})$, then any representation of $N$ that does not use $c_n$ must use at least $c_n$ coins of some smaller denomination $c_i$, so it cannot be optimal: rather than use $c_n$ coins of value $c_i$, we could use $c_i$ coins of value $c_n$. Therefore all optimal representations of $N$ use at least one coin of value $c_n$.

We can do a bit better. Call a representation obviously inefficient if it uses $c_{i+1}$ or more coins of value $c_i$, for some positive integer $i<n$. Any obviously inefficient representation cannot be optimal, since you can swap those coins for $c_i$ coins of value $c_{i+1}$ and improve it. If a representation is not obviously inefficient, and does not use any coins of value $c_n$, then its total value is at most $$(c_2-1)c_1 + (c_3-1)c_2 + (c_4-1)c_3 + \dots + (c_n-1)c_{n-1}.$$ If $N$ is greater than this value, then the optimal representation of $N$ must use at least one coin of value $c_n$.