1
$\begingroup$

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.

$\endgroup$

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.