My first Magazine pemrograman-kompetitif-dasar | Page 76

7 Dynamic Programming
Algoritma 29 Penyelesaian Coin Change secara bottom-up .
function SOLVE ()
2:
f [0] ← 0
1:
3:
4:
5:
6:
7:
8:
9:
10:
11:
for x ← 1, N do
best ← ∞
for k ← 1, M do
if (a k ≤ x) then
best ← min(best, f [x − a k ] + 1)
end if
end for
f [x] ← best
end for
return f [N]
13: end function
12:
Dengan mudah Anda dapat memperhatikan bahwa kompleksitas solusi dengan bottom-
up pada Algoritma 29 adalah O(NM). Kompleksitas ini sama seperti dengan cara top-down .
Kenyataannya, sebenarnya keduanya merupakan algoritma yang sama, hanya berbeda di arah
pencarian jawaban.
Pengisian Tabel
Cara bottom-up yang dijelaskan sebelumnya terkesan seperti "mengisi tabel". Pada bagian
ini, kita akan coba simulasikan bottom-up untuk menghitung f (12) dengan nominal koin 1, 6, dan
10 rupiah. Mula-mula, kita memiliki tabel f (x) untuk nilai x dari 0 sampai 12, seperti pada Tabel
7.1.
Tabel 7.1: Tahap 1: Siapkan tabel untuk menyimpan nilai f . Mula-mula tabel tersebut kosong.
x
0 1 2 3 4 5 6 7 8 9 10 11 12
f (x)
Tabel 7.2: Tahap 2: Isi base case yaitu f (0) = 0.
x
0 1 2 3 4 5 6 7 8 9 10 11
f (x) 0
12
Berikutnya, kita akan mengisi f (1). Satu-satunya pilihan adalah menukarkan dengan koin 1,
karena kita tidak bisa menggunakan koin 6 atau 10. Maka f (1) = f (1 − 1) + 1 = f (0) + 1. Dengan
demikian, nilai tabel akan menjadi seperti pada Tabel 7.3.
Tabel 7.3: Tahap 3: Isi tabel setelah pengisian f (1).
x
0 1 2 3 4 5 6 7 8 9 10 11 12
f (x) 0 1
Hal serupa terjadi ketika kita mengisi f (2), f (3), f (4), dan f (5). Satu-satunya pilihan adalah
66