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

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

p 166 Making Change

Post by hank » Sat Aug 31, 2002 5:04 am

Is there any algorithms to solve this problem?

Can you give me some tips? :oops:

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

Post by obayashi » Sat Aug 31, 2002 5:09 am

Code: Select all

dynamic programming
or

Code: Select all

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

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

Post by hank » Sat Aug 31, 2002 5:10 am

can you give me some tips of using DP?

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

Post by obayashi » Sat Aug 31, 2002 5:15 am

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? :lol:
Time makes a fool of memory
And yet my memories still shine

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

Post by hank » Sat Aug 31, 2002 5:28 am

What is 3 dimension DP? :cry:

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

Post by obayashi » Sat Aug 31, 2002 5:36 am

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~ :P
Time makes a fool of memory
And yet my memories still shine

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

Post by hank » Sat Aug 31, 2002 5:39 am

Thanks!!!.! :P

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

Post by hank » Sat Aug 31, 2002 2:57 pm

(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 )

:D

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

166 - Making Change

Post by bik29 » Tue Oct 08, 2002 10:50 pm

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)
{
car = System.in.read();
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]

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Sat Jul 17, 2004 1:40 pm

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

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Sat Jul 24, 2004 4:07 am

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
Output generated by your code:
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

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Sun Jul 25, 2004 9:35 pm

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

Post by Emilio » Mon Mar 28, 2005 8:18 pm

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?
Thanks in advance!

hours later

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

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Post by jagadish » Thu Aug 11, 2005 4:24 pm

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.

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Post by jagadish » Thu Aug 11, 2005 5:11 pm

AC now..i had a tiny initilization problem..
if u can think of it .. u can do it in software.

Post Reply

Return to “Volume 1 (100-199)”