I posted (searched and posted) a standard way to partition number few weeks back... (as a part of euler project).. The one liner problem was to find number of ways to split an integer as sum of other Positive integers. (http://zeektech.blogspot.com/2010/08/project-euler-76-ways-can-one-hundred.html)
I recently got similar challenge (seems to be famous problem again).. which deals with Integer partition but restricted integers to be used.
Problem: Find Ways to Split $N into $0.01, $0.05, $0.10, $0.25
Here is the solution: (obviously it again uses DP)
The code above does the same work...with memoization... The memoization (google it for details) is a way to store previous computation. The table here stores the value of previously computed recursion, hence less function calls.
The array produced finally is similar to array produced in previous post, with a slight modification.
PS: Each line of input file (passed in argument) contains value of "N" for which ways has to be counted
Happy Coding!!
I recently got similar challenge (seems to be famous problem again).. which deals with Integer partition but restricted integers to be used.
Problem: Find Ways to Split $N into $0.01, $0.05, $0.10, $0.25
Here is the solution: (obviously it again uses DP)
import java.io.*;
public class coin_changes{
public static int[] d = {1, 5, 10, 25};
public static int[][] table;
public static void main(String[] args) throws Exception{
table = new int[10000][4];
for (int i=0; i<10000; i++)
for (int j=0; j<4; j++)
table[i][j]=-1;
DataInputStream dis = new DataInputStream(new FileInputStream(new File(args[0])));
String a = dis.readLine();
while (a != null){
System.out.println(recF(Integer.parseInt(a),3));
a = dis.readLine();
}
}
public static int recF(int i, int j){
if (j < 0 || i < 0)
return 0;
if (i == 0) {
return 1;
}
if (table[i][j]!=-1)
return table[i][j];
else
table[i][j]=recF(i, j-1) + recF(i-d[j], j);
return table[i][j];
//return recF(i, j-1) + recF(i-d[j], j);
}
}
The code above does the same work...with memoization... The memoization (google it for details) is a way to store previous computation. The table here stores the value of previously computed recursion, hence less function calls.
The array produced finally is similar to array produced in previous post, with a slight modification.
PS: Each line of input file (passed in argument) contains value of "N" for which ways has to be counted
Happy Coding!!
