I asked my Advanced Algorithms professor recently if we could solve the coin change problem (least number of coins necessary to make change for S cents using denominations d1, d2, ... dk). I thought this might be possible using something like the least common multiple of the denominations to find a subset of answer that could be used to determine the whole answer, independent of the size of S.

My professor said that this is actually a very complicated problem, and there was a paper in the 90's or 2000's to that demonstrated this solution. He couldn't remember the reference for this paper, though. Could anyone provide the reference? I would be very appreciative.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.