Blognya Riza

Soal 5 Olimpiade Sains Mahasiswa 2007, Yogyakarta.

Deskripsi Soal :

Diberikan sebuah perkalian matriks, P=A*B*C*D, dengan ordo/ ukuan masing-masing A(20X50), B(50X100), C(100X10), dan D(10X30). Ada beberapa cara melakukan perkalian matriks ini, dan tiap cara mempunyai jumlah operasi perkalian yang berbeda, antara lain :

1) P=(A*B)*C*D => (20*50*100)+(20*100*10)+(20*10*30) = 126000 perkalian

2) P=A*((B*C)*D) => (50*100*10)+(50*10*30)+(20*50*30) = 95000 perkalian

3) P=A*(B*C)*D => (50*100*10)+(20*50*10)+(20*10*30) = 66000 perkalian

Ternyata jumlah operasi perkalian terkecil yang mungkin terjadi adalah 66000 perkalian, yaitu dengan P=A*(B*C)*D. Buatlah program yang menerima input 2 baris. Baris pertama adalah jumlah matriks(N) dan baris kedua berisi N+1 bilangan asli yang menyatakan ukuran matriks pada perkalian. Program harus meng-outputkan jumlah opersi perkalian terkecildari perkalian matriks tersebut.

Contoh Input 1 :

4

20 50 100 10 30

 

Contoh Output 1 :

66000

 

Contoh Input 2 :

3

1 4 7 5

 

Contoh Output 2 :

63

 

Solusi :

Dalam perkalian dua matriks A(mxn) dan B(nxo) akan menghasilkan matriks baru C dengan ukuran (mxo). Sedangkan jumlah operasi perkaliannya adalah (m*n*o).

Awalnya saya berpikir untuk mengalikan 2 matriks A(mxn) dan B(nxo) dengan nilai n terbesar, sehingga nilai n hilang dan tidak dipakai lagi dalam perkalian matriks berikutnya(greedy). Tapi ternyata algoritma itu tidak menghasilkan nilai minimum untuk contoh input ke-2. Jadi saya beralih ke DP, meskipun kompleksitasnya lumayan besar, sekitar O((n+1)^3/2).

 

Formula DPnya kira-kira seperti ini :

Untuk data ukuran matriks i sampai j, nilai awal min[i,j] adalah ∞.

Kemudian untuk k= i+1 sampai j-1,

tmp:=min[i,k]+min[k,j]+(data[i]*data[k]*data[k])

            jika tmp<min[i,j], maka min[i,j]=tmp

 

Tenti saja kita harus mencari nilai min[i,k] dan min [k,j] terlabih dahulu. Dengan kata lain, formula DP diatas harus dilakukan pada selisih i dan j yang terkecil terlebih dahulu. Kita definisikan bahwa min[i,i+1]:=0 (karena merupakan data satu matriks saja) dan min[i,i+2]=data[i]*data[i+1]*data[i+2] (karena hanya mencakup 2 matriks saja, yaitu matriks A(data[i]xdata[i+1]) dan matriks B(data[i+1],data[i+2]))

Kira-kira kode Pascalnya seperti ini :

 

var data:array[1..100] of integer;

    min:array[1..100,1..100] of longint;

    k,i,j,n,selisih:integer;

    tmp:longint;

 

begin

  readln(n);

  n:=n+1;

  for i:=1 to n do

    read(data[i]);

 

  for selisih:=2 to n-1 do

    for i:=1 to n-selisih do

      begin

        j:=i+selisih;

        min[i,j]:=high(longint);

        for k:=i+1 to j-1 do

          begin

            tmp:=min[i,k]+min[k,j]+(data[i]*data[k]*data[j]);

            if tmp<min[i,j] then

              min[i,j]:=tmp;

          end;

      end;

 

  writeln(min[1,n]);

end.