Personal computing discussed
Moderators: renee, SecretSquirrel, just brew it!
Hawkwing74 wrote:My knowledge of the subject is peripheral at best, but I'm curious. If you're going for speed why use a class? I would think constructing the class object would take some time. Or does Java require a class?
UberGerbil wrote:Does it have to be in Java?
for(j=0;j<=((cash-money)/10);j++)
{
// money+=(10*j);
// k=((cash-money)/5);
// if(total()==cash)
numTimes++;
// money-=(10*j);
}
just brew it! wrote:"How many ways can I make change for $1 using only 50 cent or smaller coins?" thousands (maybe even millions) of times. The cache array guarantees that that computation -- and every other possible "How do I make change for x using only y or smaller coins?" sub-computation -- is done once, and only once. This improves the efficiency of the brute force approach by many orders of magnitude (at the cost of a couple of megabytes of additional RAM to store the cache array).
import java.io.*;
import java.util.*;
class Money{
public static final int MAX_CENTS = 30000;
static final int values[] = { 10000, 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 0 };
static final long cache[][] = new long[ values.length ][ MAX_CENTS + 1 ];
public static void main (String []args){
long beginTime = System.currentTimeMillis();
try {
BufferedReader in = new BufferedReader (new FileReader ("D:\\Money\\src\\dollars.txt"));
String s = in.readLine();
while (s != null)
{
int cents = (int)(Double.parseDouble( s ) * 100);
System.out.println( s + "\t" + maxWaysToMake( 0, cents ) );
s = in.readLine();
}
} catch (Exception e) {
System.out.println(e);
}
System.out.println( "Elapsed milliseconds: " + ( System.currentTimeMillis() - beginTime ) );
}
public static long maxWaysToMake(int start, int target)
{
// Check for trivial terminal conditions and compute value if needed
if (values[start] == 0)
return 0;
else if (target == 0)
return 1;
else if (cache[start][target] != 0)
return cache[start][target];
else
return (cache[start][target] = ((values[start] <= target)
? maxWaysToMake(start, target - values[start]) : 0)
+ maxWaysToMake(start + 1, target));
}
}
Hawkwing74 wrote:Amazing you should teach advanced C++ or something. (of course they don't make any money I suppose)
moog wrote:Nice way to do it.
Yahoolian wrote:I can see that JBI like the tertiary operator... (So do I.)
I ported it to java.
long beginTime = System.currentTimeMillis();
System.out.println( "Elapsed milliseconds: " + ( System.currentTimeMillis() - beginTime ) );
Yahoolian wrote:Performance seems to be comparable. It says 0 milliseconds elapsed, when I addat the beginning of main andCode: Select alllong beginTime = System.currentTimeMillis();
after main, it says 0.Code: Select allSystem.out.println( "Elapsed milliseconds: " + (beginTime - System.currentTimeMillis()) );
From my limited testing, results are the same.
So the algorithm takes less time to execute than the granularity of your system's time-of-day clock. Cool!
Come to think of it, when I reported my 30ms time, I was using the Linux (well actually Cygwin) 'time' command to clock execution of the program... so that 30ms figure actually includes program load time!
BTW Yahoolian... if Java 'int' data type is 32 bit signed, the program will fail for input values greater than 62... that's why I used doubles in the C++ version.
Yahoolian wrote:From my limited testing, results are the same.
The other cute thing about this version is that you can change the denominations of currency used in the simulation just by changing the values in the array -- the code is completely generic. E.g, if you want to include pennies, all you need to do is add a 1 to the array between the 5 and the 0...
static double cache[11][MAX_CENTS + 1];
Yahoolian wrote:Well you'd also have to change the 11 to a 12 in the line below. A nice feature of java is that arrays know their length.Code: Select allstatic double cache[11][MAX_CENTS + 1];
static double cache[sizeof(values) / sizeof(values[0])][MAX_CENTS + 1];
else
return (cache[start][target] = ((values[start] <= target)
? maxWaysToMake(start, target - values[start]) : 0)
+ maxWaysToMake(start + 1, target));