## 166 - Making Change

Moderator: Board moderators

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

### p 166 Making Change

Is there any algorithms to solve this problem?

Can you give me some tips?

obayashi
New poster
Posts: 33
Joined: Thu Jun 20, 2002 1:18 pm

Code: Select all

``````dynamic programming
``````
or

Code: Select all

``````branch and bound
``````
Time makes a fool of memory
And yet my memories still shine

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
can you give me some tips of using DP?

obayashi
New poster
Posts: 33
Joined: Thu Jun 20, 2002 1:18 pm
usually such program can be solved by 2 or 3 dimension DP.

but i use recursion and branch and bound.
to search for the result, the upper bound will descend step by step while program recurses... so the total search amount won't be large.

get it?
Time makes a fool of memory
And yet my memories still shine

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
What is 3 dimension DP?

obayashi
New poster
Posts: 33
Joined: Thu Jun 20, 2002 1:18 pm

Code: Select all

``````for
for
for {

}

eg. the Floyd algorithm is a typical/classic 3D DP :lol:
``````
and there's some way to convert recursion to iteration(dp)
such as matrix chain multipulation (problem 348, i used both recursion and iteration)...

good luck~
Time makes a fool of memory
And yet my memories still shine

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
Thanks!!!.!

hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.
(poor english~~^ _ *)

I solved this problem by "Branch and Bound" this afternoon.
But it got accepted in 1.450 seconds.
It is not efficient.
How to solve the problem faster? ( < 0.1 seconds )

bik29
New poster
Posts: 1
Joined: Tue Oct 08, 2002 10:40 pm

### 166 - Making Change

Hi,
I have been trying to solve this problem with the following algorithm:

1. Keep an array of size 10000 (big enuf I think) and calculate the minimum number of coins needed to make an amount between 1 and 10000 ( -1 if it is not possible), assuming that all the denominations are available in infinite amounts.

2. For each amount producible by the existing coins by the user, if that amount >= target, I update my resullt =
min (result, count + min [amount-target]) .

Somehow I keep getting WA.

Some one please highlight where I am doing wrong. Code is appended below.

[java]

import java.io.*;
import java.util.*;
class Main
{
static String ReadLn (int maxLg) // utility function to read from stdin
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}

if ((car < 0) && (lg == 0)) return (null); // eof
return (new String (lin, 0, lg));
}

public static void main (String args[]) // entry point from OS
{
Main myWork = new Main(); // create a dinamic instance
myWork.Begin(); // the true entry point
}
int[] den = {5,10,20,50,100,200};
int[] min = new int[100001];

void Begin()
{
String input;
StringTokenizer idata;

for(int i =0 ; i < min.length; i++) min = -1;

min[0] = 0;

for(int i = 0; i < den.length; i++) {
for(int j = den; j < min.length; j++) {
if( min[j-den] >= 0) {
if( min[j] < 0 || min[j] > min[j-den]+1) {
min[j] = min[j-den]+1;
}
}
}
}

while ((input = Main.ReadLn (255)) != null)
{
idata = new StringTokenizer (input);
int[] c = new int[6];
boolean end = true;
for(int i = 0; i < 6; i++)
if( (c = Integer.parseInt(idata.nextToken()))
!= 0) end = false;

if(end) break;
double t = Double.valueOf(idata.nextToken()).doubleValue();

int tot = (int) (t * 100);
res = Integer.MAX_VALUE;
doit(c, 0, 0, 0, tot);

String r = res+"";
while(r.length() < 3) r = " "+r;
System.out.println(r);
}
}
int res;

void doit(int[]c, int level, int count, int ct, int tot) {
if ( ct >= tot || level == c.length) {
if(ct - tot > 10000) return;
if(ct < tot) return;
if( count + min[ct-tot] >= res) return;
res = Math.min(res,count+min[ct-tot]);
if( level == c.length) return;
}
for(int i =0; i <= c[level]; i++) {
doit(c, level+1, count+i, ct + i * den[level], tot);
}
return;

}

}
[/java]
[/java]

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
Here you have some random input.
8 0 3 3 7 8 1.65
0 0 6 7 8 0 3.15
6 2 1 7 1 0 0.8
1 9 3 4 9 0 0.85
4 5 8 3 4 2 2.65
7 1 8 4 0 3 2.25
0 6 3 3 9 3 4.75
7 9 1 4 5 6 4.7
3 1 0 7 4 9 3.15
2 8 5 6 3 2 0.75
5 3 9 9 8 6 0.1
6 5 2 8 5 4 1.05
7 0 1 3 8 3 0.7
4 3 2 1 4 2 0.1
9 0 1 8 4 9 3.8
4 6 2 6 0 3 1.75
1 6 3 4 7 1 2.65
9 6 0 3 0 3 2.8
5 3 7 8 5 0 4.75
8 7 7 4 6 1 4.05
3 4 2 9 1 5 2.85
9 4 4 0 7 5 0.1
3 9 0 8 6 3 2.6
6 8 5 1 9 6 3.5
4 5 9 0 7 5 2.2
7 8 4 5 1 7 2
0 5 5 1 6 1 3.75
2 9 3 4 8 7 0.4
3 1 5 7 3 9 4.55
8 8 2 8 9 6 0.55
5 2 5 8 9 6 4.85
0 9 0 9 3 2 0.25
4 3 1 7 2 2 2.05
6 0 1 3 9 0 4.1
9 9 6 1 4 1 4.5
4 1 9 0 0 1 3.45
8 9 4 4 0 2 1.7
2 6 8 8 6 3 5
7 4 3 6 8 7 0.85
4 3 1 2 5 9 0.3
2 8 3 1 5 9 2.45
6 2 9 8 6 3 2.4
9 9 8 8 2 3 0.05
6 7 9 2 9 9 0.95
0 4 0 9 1 6 0.6
3 2 2 7 9 3 3.8
6 7 3 8 3 9 3.15
1 6 0 6 7 7 1.6
1 6 7 5 4 6 1.7
5 5 7 3 0 2 1.2
3 5 7 6 9 7 0.2
9 3 4 3 8 9 0.1
3 1 1 9 9 5 2.35
1 0 8 8 8 0 4.95
6 9 8 2 6 1 0.9
6 4 6 8 5 7 2.95
2 5 6 5 1 8 1.4
8 8 0 4 9 6 0.65
0 7 5 5 1 8 3.8
0 1 2 8 9 7 0.95
6 8 9 1 6 9 4.15
5 5 8 1 1 3 4.8
1 7 4 0 1 3 1.45
4 3 3 0 0 7 0.6
4 6 4 1 6 3 3.85
8 1 0 6 1 5 1.1
7 5 9 5 3 7 1.5
9 1 7 6 6 6 4.45
5 1 3 2 3 2 1.65
1 9 8 1 9 2 0.55
7 9 5 5 5 4 0.45
9 6 7 3 3 9 1.15
8 7 1 9 3 3 2.05
0 6 8 7 8 8 2.05
5 7 5 9 1 9 4.15
6 4 0 7 3 5 4.3
6 6 6 2 8 6 4.75
4 2 3 9 8 2 2
1 9 7 4 4 2 4.4
0 8 8 8 8 7 1.5
2 0 2 5 0 3 4.35
7 7 9 6 9 4 4.85
6 7 1 9 5 9 3.55
5 0 9 1 7 6 0.3
4 9 6 3 8 6 1.3
8 6 8 4 2 0 1.45
3 6 0 6 4 7 1.65
5 5 3 6 8 4 4.65
4 9 2 7 6 5 4.6
5 0 2 0 2 9 3.15
7 2 2 8 1 8 3.8
8 4 7 2 9 9 3.75
9 7 5 0 8 0 3.05
7 8 7 2 8 3 0.95
8 7 9 3 9 6 1.85
2 9 7 9 7 3 0.8
8 2 6 1 0 7 0.8
5 4 9 8 9 2 4.95
5 3 2 4 6 4 2.75
6 5 8 6 7 8 0.7
3 4 2 0 1 8 2.95
1 3 3 8 0 9 1.35
7 4 8 8 2 1 4.75
3 4 1 2 6 7 4.75
6 2 0 3 0 3 3.6
7 9 1 1 7 1 0.35
2 4 5 4 3 5 1.9
8 1 5 5 8 1 0.95
1 6 2 0 0 7 3.35
2 6 4 1 9 6 3.8
8 4 9 6 0 4 2
1 1 7 1 2 7 0.25
0 1 4 4 5 9 0.65
2 4 5 9 5 7 0.75
9 3 7 2 9 2 3.5
2 7 7 5 1 5 3.65
0 1 5 3 9 6 2.9
0 1 8 8 8 5 0.15
6 9 8 3 2 1 3.7
4 3 8 5 6 5 3
9 7 8 5 0 7 2.9
8 8 7 6 0 7 1.45
5 9 4 5 8 8 5
7 2 4 4 3 4 0.2
0 5 1 0 1 9 1.55
0 6 5 3 9 3 2.95
8 2 6 1 7 3 3.5
6 9 3 7 3 8 4.95
8 8 4 4 7 1 2.1
8 4 4 5 7 2 3.2
0 7 0 1 8 6 4.85
2 0 3 9 3 5 4.2
0 8 5 5 7 3 1.4
9 0 8 4 3 3 4.6
8 6 9 6 8 1 0.05
9 7 6 0 3 6 0.35
8 2 2 1 7 7 2.9
2 1 0 7 3 0 1.15
9 3 5 6 8 9 3.1
2 6 5 9 7 6 0.1
0 6 3 0 6 5 0.4
5 7 7 1 4 5 2.2
7 9 6 3 7 1 0.45
6 5 7 4 2 6 3.75
7 4 9 8 1 2 3.35
6 2 1 1 7 8 4.6
7 6 3 9 0 2 4.45
5 2 9 7 0 3 3.9
5 4 9 4 3 4 1.5
2 7 3 0 9 8 3.5
0 7 0 9 1 1 0.3
3 1 7 1 8 3 1.2
4 6 9 5 9 8 3.75
9 7 8 3 9 6 0.95
8 4 9 0 2 6 1.6
2 9 4 5 0 3 4
2 9 0 2 2 5 4.1
1 6 1 3 0 0 1.15
2 8 4 7 8 5 1.55
7 4 4 8 8 1 4.35
4 5 1 2 4 6 1.25
1 2 0 9 3 9 0.95
1 7 4 7 3 0 2.45
3 5 9 8 5 6 2.15
1 5 5 0 0 4 0.35
6 0 9 1 0 1 2.75
8 6 4 7 0 1 3.4
5 2 7 5 9 9 4.7
6 6 1 7 9 0 3.45
1 7 5 7 0 2 2.3
7 3 5 0 4 7 3.65
7 1 0 0 7 6 4.65
9 7 4 1 7 5 1.4
1 6 9 1 0 2 4.3
4 9 8 5 7 4 0.45
7 3 5 4 1 6 4.35
4 2 0 9 3 0 0.2
0 9 3 3 8 5 4.1
1 0 6 0 0 2 4.55
2 6 3 8 3 6 0.25
6 7 3 7 2 9 3.1
8 0 6 8 7 2 1
8 1 1 3 5 5 2.6
0 7 6 6 5 4 2.95
6 7 7 3 1 2 2.9
2 2 2 8 1 4 5
7 8 7 1 4 6 1.8
9 0 1 4 8 4 2.75
5 6 4 6 2 2 3.9
1 7 6 1 6 4 5
5 5 4 0 5 9 3.55
2 6 3 9 8 0 0.1
5 3 4 2 0 6 1.9
3 9 3 3 1 7 0.95
2 2 5 4 6 1 4.4
9 1 4 7 9 9 0.25
3 8 9 7 7 8 0.05
5 6 2 7 5 8 4.2
0 3 8 8 6 8 1.15
1 5 7 0 8 5 2.35
0 0 0 0 0 0
4
5
2
3
4
3
5
4
4
3
1
2
2
1
3
3
4
4
7
4
4
1
3
3
2
1
5
2
4
2
5
3
2
6
4
9
3
3
3
2
3
3
1
2
2
3
4
3
3
3
1
1
4
6
2
3
3
3
3
2
4
4
3
3
4
2
2
4
4
2
2
3
2
3
4
4
5
1
4
2
5
5
4
2
3
3
4
5
4
4
3
4
4
2
3
2
3
4
4
2
3
4
6
5
4
3
2
2
5
3
1
2
3
3
3
5
3
2
4
2
4
3
3
1
3
3
3
4
2
3
5
3
3
5
1
3
3
3
3
1
2
2
2
4
5
4
4
3
2
3
2
2
4
2
3
2
3
4
3
6
3
2
4
3
3
4
5
4
5
3
5
6
3
4
2
5
2
3
6
2
3
1
3
3
3
3
2
4
3
3
4
1
2
2
5
2
1
3
3
4

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
Input:
6 0 4 3 7 3 1.40
4 7 2 2 5 2 1.80
9 2 0 8 1 8 3.30
0 5 2 5 2 7 0.75
4 3 1 2 8 7 4.80
5 2 7 2 1 8 4.15
9 4 7 3 3 3 0.70
1 8 8 0 7 4 3.10
6 7 5 4 6 3 2.60
1 7 7 9 7 7 4.80
9 3 1 3 2 0 3.80
7 3 5 5 9 9 1.35
1 7 2 5 0 9 3.45
8 4 7 5 2 0 2.00
6 0 4 8 7 0 0.95
0 6 3 3 5 3 3.00
6 2 8 2 0 5 3.65
8 5 9 6 2 7 0.10
0 7 5 9 9 1 2.10
7 2 0 7 5 6 1.00
6 9 1 5 6 7 1.10
8 7 4 6 6 8 0.95
5 0 4 9 9 6 3.40
2 6 2 2 8 4 1.55
6 0 2 2 2 8 1.35
8 2 7 6 5 5 0.70
8 1 7 2 9 2 1.15
4 6 7 3 4 3 4.40
8 0 5 3 3 5 3.10
2 6 0 5 3 3 2.75
5 5 6 9 0 3 0.80
5 7 7 5 2 5 4.35
8 1 7 4 8 8 3.95
6 9 1 6 2 2 0.50
6 6 0 4 4 1 2.65
3 9 6 6 2 9 1.40
2 1 6 7 4 8 3.85
2 2 8 0 5 7 2.35
2 1 9 4 1 0 4.25
3 8 0 3 2 6 2.40
5 8 5 9 6 5 2.30
6 4 7 7 6 3 0.30
4 5 1 2 6 6 4.50
9 8 0 0 7 3 0.40
2 9 4 7 9 0 1.80
8 5 0 9 4 1 3.55
7 2 9 1 1 8 4.35
2 9 0 4 2 4 4.70
5 2 5 3 4 5 3.45
4 9 3 7 1 8 3.80
4 6 9 5 5 2 3.65
6 7 1 1 6 2 1.00
6 2 5 2 4 3 0.80
9 8 4 4 1 2 3.35
4 5 6 3 0 6 1.40
4 3 7 9 3 0 4.20
1 5 9 4 1 8 3.35
2 9 1 7 5 7 3.55
5 4 1 1 6 5 2.20
9 0 6 7 5 8 3.45
4 7 3 9 2 0 3.85
7 9 9 7 0 7 2.45
0 4 8 6 2 4 3.75
6 6 4 8 2 9 3.40
7 6 4 0 6 8 0.60
9 4 9 6 6 5 4.60
4 3 5 8 7 8 0.55
5 2 1 9 7 8 3.50
6 0 6 7 5 7 3.20
6 5 8 4 1 9 3.70
3 7 8 3 8 3 0.35
2 7 2 8 9 3 1.60
2 0 3 7 7 8 1.15
7 9 7 6 9 2 0.35
1 8 9 7 7 4 4.00
6 9 4 4 5 6 2.10
6 9 9 2 4 7 4.45
4 7 6 7 0 2 1.40
9 2 4 1 0 4 1.60
5 5 3 0 9 2 4.15
5 6 1 3 0 0 1.40
6 3 0 0 6 2 2.50
9 8 9 6 6 1 2.20
8 5 0 2 2 8 3.20
1 6 2 0 1 7 1.40
5 3 9 9 4 3 2.00
3 1 0 6 2 0 1.80
4 7 9 5 9 3 4.65
7 2 4 4 0 8 2.75
9 1 5 3 9 0 4.20
8 6 8 2 9 0 1.40
1 9 5 7 8 1 3.00
1 0 8 9 1 0 4.15
2 6 4 3 9 7 3.50
2 9 5 7 7 7 2.65
9 2 6 3 5 9 4.30
0 8 0 4 9 2 2.75
5 5 0 3 9 7 2.75
7 8 2 7 0 9 2.70
0 0 0 0 0 0
My output:
3
2
4
3
4
4
2
3
3
4
7
4
4
2
2
2
5
1
2
1
2
2
4
3
4
2
3
4
4
4
3
5
3
1
4
3
4
4
12
3
3
2
3
3
3
4
5
5
4
3
5
1
2
5
3
6
5
4
2
4
8
3
4
4
3
4
2
3
3
4
3
3
3
3
2
2
4
3
3
4
4
3
2
4
3
1
3
5
4
5
3
2
9
3
4
4
4
4
3
4
2
5
3
5
4
3
3
3
5
7
4
4
2
2
2
4
1
2
1
2
2
5
3
4
3
2
4
4
4
3
4
3
1
3
4
4
4
12
4
3
2
3
3
3
3
4
5
4
4
4
1
2
5
4
6
5
3
2
4
8
3
4
5
3
4
2
3
3
4
2
3
3
2
2
2
4
4
3
4
5
3
2
4
4
1
4
5
4
5
4
2
9
3
3
4
4
4
3

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
No, I didn't swap the output sets. I compiled your code on gcc 2.95 with -Wall -ansi -pedantic options.

BTW - I guess I've just fount your mistake.
[c]v=(int)(value*20.0); [/c]
This is a very, very bad idea. You should know that float numbers have only finite precision, so it is possible that 1.0 * 20 < 20.0. The difference is small, but significant enough to round 1.0 * 20 to 19. Try this instead:
[c]v = (int)(value * 20.0 + 0.5)[/c]Constant 0.5 is ok, 0.0001 is fine too.
When I fixed that, there is still a difference on 87-th input set though.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

### P166 Making Change

Hello,
I'm learning dinamic programming now, and I want to do this problem with this technique.
Can anyone say me how solve it with DP?
I have tried it but I get WA, and I have tried some test cases of the board and can't obtain the correct answers.
Can anyone describe me any algorithm to solve it, please?

hours later

I have obtained AC using DP, anyway some method, algorithm, ... will be welcome

Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA
getting WA again and again..whats the max value of amount i should bother to make change for ? [ i guess its only upto 6.00 ]

Input

Code: Select all

``````0 0 0 0 0 3 5.00
0 0 0 1 1 2 4.05
0 1 0 0 0 1 1.65
100 0 1 0 0 1 1.35
0 0 0 0 0 1 1.15
0 0 0 0 0 1 0.35
0 1 1 3 1 0 1.35
100 1 1 2 0 0 1.50
1 1 1 3 2 0 1.35
1 1 1 3 1 0 1.35
0 1 1 3 1 1 1.35
5 1 1 4 1 0 2.15
1 1 7 3 1 30 4.35
0 0 0 1 1 0 0.05
0 0 0 0 0 1 0.05
0 0 0 1 0 1 0.05
0 1 0 0 1 0 0.05
0 0 0 0 0 1 0.15
0 0 0 0 0 1 1.15
0 0 0 0 1 1 2.15
0 0 0 0 0 2 3.15
0 0 0 0 0 1 0.95
0 0 0 0 0 1 1.95
0 0 1 3 1 0 0.15
0 1 0 3 1 0 0.35
99 0 0 0 0 1 5.00
99 0 0 0 0 0 4.95
99 1 0 0 1 0 4.95
9  1 1 2 1 2 4.95
0 0 0 0 0 0

``````
Output :

Code: Select all

``````
4
6
4
4
5
5
4
8
4
4
4
5
5
4
6
4
2
6
5
6
6
3
2
2
3
61
99
79
4

``````
if u can think of it .. u can do it in software.