My first Magazine pemrograman-kompetitif-dasar | Page 77

7.1 Konsep Dynamic Programming
menukarkan dengan koin 1, karena kita tidak bisa menggunakan koin 6 atau 10. Sehingga,
f (2) = f (1) + 1, f (3) = f (2) + 1, dan seterusnya. Dengan demikian, nilai tabel akan menjadi
seperti pada Tabel 7.4.
Tabel 7.4: Tahap 4: Isi tabel setelah pengisian f (2) sampai f (5).
x
0 1 2 3 4 5 6 7 8 9 10 11 12
f (x) 0 1 2 3 4 5
Langkah berikutnya adalah mengisi f (6). Kali ini, terdapat pilihan untuk menggunakan koin 1
atau 6 terlebih dahulu, sehingga:
f (6) = min( f (6 − 1) + 1, f (6 − 6) + 1)
= min( f (5) + 1, f (0) + 1)
= min(5 + 1, 0 + 1)
= min(6, 1)
= 1
Memang benar, untuk membayar 6 kita hanya membutuhkan 1 koin. Dengan demikian, nilai
tabel menjadi seperti pada Tabel 7.5.
Tabel 7.5: Tahap 5: Isi tabel setelah pengisian f (6).
x
0 1 2 3 4 5 6 7 8 9 10 11 12
f (x) 0 1 2 3 4 5 1
Lakukan hal serupa untuk x = 7 sampai x = 9. Saat pengisian f (10), terdapat pilihan untuk
menggunakan koin 1, 6, atau 10 terlebih dahulu, sehingga:
f (10) = min( f (10 − 1) + 1, f (10 − 6) + 1, f (10 − 10) + 1)
= min( f (9) + 1, f (4) + 1, f (0) + 1)
= min(4 + 1, 4 + 1, 0 + 1)
= min(5, 5, 1)
= 1
Kembali, dapat dicek bahwa untuk membayar 10 kita hanya membutuhkan 1 koin, yaitu
langsung menggunakan koin 10 (tanpa 1 dan 6). Kita dapat lakukan hal serupa untuk pengisian
f (11) dan f (12) sebagai berikut:
f (11) = min( f (11 − 1) + 1, f (11 − 6) + 1, f (11 − 10) + 1)
= min( f (10) + 1, f (5) + 1, f (1) + 1)
= min(1 + 1, 5 + 1, 1 + 1)
= min(2, 6, 2)
= 2
67