Question

LANGUAGE: JAVA (using greedy algorithm)

Implement a dynamic programming solution to identify the least-cost way of performing a chained matrix multiplication. (this part is just for reference, need the code for below).

(I want this second part to be solved using greedy algo)--> Also implement, to compare the costs, greedy way of performing chained matrix multiplication

Answer 1

//greedy way of performing chained matrix multiplication

class ChainMultiplication
{

static int MatChainOrder(int q[], int a, int b)

{

if (a == b){

return 0;

}

int minimum = Integer.MAX_VALUE;

for (int c=a; c<b; c++)

{ int count = MatChainOrder(q, a, c) + MatChainOrder(q, c+1, b) + q[a-1]*q[c]*q[b];

if (count < minimum)

minimum = count;

}

return minimum;

}

public static void main(String args[])

{ int array[] = new int[] {1, 2, 3, 4, 3};

int d = arr.length;

System.out.println("Minimum number of multiplications is "+ MatChainOrder(array, 1, d-1));

}
}