On a variant of the change-making problem
Adam N. Letchford, Licong Cheng · Operations Research Letters · 2024
The change-making problem (CMP), introduced in 1970, is a classic problem in combinatorial optimisation. It was proven to be NP -hard in 1975, but it can be solved in pseudo-polynomial time by dynamic programming . In 1999, Heipcke presented a variant of the CMP which, at first glance, looks harder than the standard version. We show that, in fact, her variant can be solved in polynomial time.