166 - Making Change

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

Re: 166 - Making Change

Post by Repon kumar Roy » Mon Oct 20, 2014 1:03 pm

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

rafastv
New poster
Posts: 22
Joined: Tue Jun 19, 2007 3:18 am

Re: 166 - Making Change

Post by rafastv » Sat Aug 12, 2017 5:05 am

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.

Post Reply

Return to “Volume 1 (100-199)”