-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathOptimalTreeSearch.java
70 lines (58 loc) · 2.13 KB
/
OptimalTreeSearch.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
public class OptimalTreeSearch {
public int minCostRec(int input[],int freq[]){
return minCostRec(input,freq,0,input.length-1,1);
}
private int minCostRec(int input[],int freq[],int low,int high,int level){
if(low > high){
return 0;
}
int min = Integer.MAX_VALUE;
for(int i=low; i <= high; i++){
int val = minCostRec(input,freq,low,i-1,level+1) +
minCostRec(input,freq,i+1,high,level+1)
+ level*freq[i];
if(val < min){
min = val;
}
}
return min;
}
public int minCost(int input[], int freq[]){
int T[][] = new int[input.length][input.length];
for(int i=0; i < T.length; i++){
T[i][i] = freq[i];
}
for(int l = 2; l <= input.length; l++){
for(int i=0; i <= input.length-l; i++){
int j = i + l -1;
System.out.println("i=="+i+" j==="+j);
T[i][j] = Integer.MAX_VALUE;
int sum = getSum(freq, i, j);
System.out.println("SUM IS---"+sum);
for(int k=i; k <= j; k++){
int val = sum + (k-1 < i ? 0 : T[i][k-1]) +
(k+1 > j ? 0 : T[k+1][j]) ;
System.out.println("val---"+val +" k--"+k+" j---"+j);
if(val < T[i][j]){
T[i][j] = val;
}
}
}
}
return T[0][input.length-1];
}
private int getSum(int freq[], int i, int j){
int sum = 0;
for(int x = i; x <= j; x++){
sum += freq[x];
}
return sum;
}
public static void main(String args[]){
int input[] = {10,12,16,21};
int freq[] = {4,2,6,3};
OptimalTreeSearch ots = new OptimalTreeSearch();
System.out.println(ots.minCost(input, freq));
System.out.println(ots.minCostRec(input, freq));
}
}