My first Magazine pemrograman-kompetitif-dasar | Page 75

7.1 Konsep Dynamic Programming
Algoritma 28 Penyelesaian Coin Change secara top-down .
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
function SOLVE (x)
if (x = 0) then
return 0
end if
if computed[x] then
return memo[x]
end if
best ← ∞
for k ← 1, M do
if (a k ≤ x) then
best ← min(best, SOLVE (x − a k ) + 1)
end if
end for
computed[x] ← true
memo[x] ← best
return best
end function
. Sudah pernah dihitung, langsung kembalikan
. Tandai bahwa sudah pernah dihitung
. Simpan hasil perhitungan
Algoritma 28 merupakan implementasi penyelesaian Coin Change dengan memoisasi. Asum-
sikan untuk menghitung suatu nilai f (x), kita membutuhkan O(M) iterasi. Maka, untuk menghitung
nilai f (x) untuk seluruh x, kita membutuhkan O(NM) operasi. Banyaknya operasi ini polinomial
terhadap N dan M, dan jauh lebih cepat daripada solusi rekursif sebelumnya.
Analisis Top-down
Top-down merupakan transformasi alami dari rumus rekursif, sehingga biasanya mudah
diimplementasikan. Urutan pengisian tabel tidak penting dan hanya menghitung nilai dari fungsi
jika hanya diperlukan. Ketika seluruh tabel memo pada akhirnya terisi, bisa saja lebih lambat
karena adanya overhead pemanggilan fungsi.
7.1.2 Bottom-up
Pada bottom-up , penyelesaian masalah dimulai dari kasus yang kecil. Ketika merumuskan
rumus rekursif, kita mengetahui jawaban kasus yang paling kecil, yaitu base case . Informasi ini
digunakan untuk menyelesaikan kasus yang lebih besar. Bottom-up biasanya dianalogikan dengan
pengisian "tabel DP". Berbeda dengan top-down , bottom-up ini dilakukan secara iteratif.
Kali ini kita akan mencoba menyelesaikan Coin Change secara bottom-up . Pada bottom-up ,
kita hitung semua nilai f (x) untuk semua nilai x dari 0 sampai N secara menaik. Nilai dari f (x)
disimpan dalam array f [x].
65