My first Magazine pemrograman-kompetitif-dasar | Page 74

7 Dynamic Programming
f (12)
f (2)
f (6)
f (0)
f (1)
f (0)
f (11)
f (5)
f (4) f (1) f (5)
... f (0) f (4)
...
f (10)
f (0)
f (4) f (9)
... ...
Gambar 7.1: Pohon rekursi setelah pemanggilan f (12).
II Sekilas Info JJ
Pada penulisan program, nilai ∞ dapat diwujudkan dengan nilai yang mendekati batas
atas tipe data bilangan. Misalnya pada integer 32 bit, nilai yang dapat digunakan adalah
2.000.000.000. Nilai ini dapat disesuaikan menjadi nilai yang lebih besar atau kecil,
bergantung pada soal dan mungkin-tidaknya nilai ini dioperasikan untuk menghindari integer
overflow.
Jawaban akhirnya ada pada SOLVE (N).
Mari kita lihat pohon rekursi yang dihasilkan oleh fungsi f . Pohon rekursi untuk f (12) dengan
nominal koin 1, 6, dan 10 rupiah dapat dilihat pada Gambar 7.1.
Jika diperhatikan pada pohon rekursi, terdapat O(M) cabang untuk setiap pemanggilan
f . Untuk menghitung nilai f (N), kita akan memiliki pohon rekursi yang kira-kira sedalam O(N).
Berarti kira-kira dilakukan O(M N ) pemanggilan fungsi. Karena itu, solusi ini membutuhkan O(M N )
operasi, yang mana banyaknya operasi ini eksponensial.
Biasanya solusi eksponensial berjalan sangat lambat. Cobalah Anda hitung nilai O(M N )
dengan M = 3 dan N = 100, untuk menyadari betapa lambatnya solusi ini! Tentu kita tidak ingin
memiliki solusi eksponensial pada pemrograman kompetitif, kecuali pada soal-soal tertentu yang
tidak memiliki solusi polinomial. Karena itu, kita harus melakukan sebuah optimisasi.
Optimasi dengan Memoisasi
Jika diperhatikan, ternyata banyak f (x) yang dihitung berkali-kali. Sebagai contoh, f (5) dan
f (4) pada pohon rekursi di Gambar 7.1 muncul berkali-kali. Kita dapat melakukan memoisasi
agar nilai f (x) hanya dihitung tepat satu kali saja.
Perhatikan bahwa hanya ada N + 1 kemungkinan x untuk f (x), yaitu 0 sampai N. Kita dapat
mencatat hasil perhitungan f (x) setelah menghitungnya.Jika suatu ketika kita kembali memerlukan
nilai f (x), kita tidak perlu menghitungnya kembali.
64