166 - Making Change

[hank]

Is there any algorithms to solve this problem?

Can you give me some tips?

[obayashi]

Code: Select all

dynamic programming

or

Code: Select all

branch and bound

[hank]

can you give me some tips of using DP?

[obayashi]

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?

[hank]

What is 3 dimension DP?

[obayashi]

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~

[hank]

Thanks!!!.!

[hank]

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

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]

[Krzysztof Duleba]

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]

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

[Krzysztof Duleba]

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]

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


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

[jagadish]

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

[jagadish]

AC now..i had a tiny initilization problem..