Page 3 of 3

Re: 166 - Making Change

Posted: Mon Oct 20, 2014 1:03 pm
by Repon kumar Roy
Be sure about multiplication :)
cin>>toMake;
n = 100 * p;

sometimes it does not work as expected .
for input like
1 1 1 1 1 1 2.05
i found n = 204

So be sure of that

Re: 166 - Making Change

Posted: Sat Aug 12, 2017 5:05 am
by rafastv
Hi, there, just so you know this is a classic DP problem, the Change-making problem. You can find the solution for unlimited coins in the YT (YouTube), for the limited case, I recommend taking the most coins possible for each value. And you will need a prune strategy, since the amount of change grow until the maximum of coins available. I've used twice the smallest value for my AC code.