My first Magazine pemrograman-kompetitif-dasar | Page 73

7.1 Konsep Dynamic Programming
solusi kasus yang lebih kecil belum ada, maka kita akan mencarinya terlebih dahulu, lalu mencatat
hasilnya. Hal ini dilakukan secara rekursif.
Pada soal Coin Change , anggaplah kita membayar N rupiah dengan koin-koin satu per
satu. Pastilah terdapat koin pertama yang kita bayarkan. Jika nilai koin itu adalah a k , maka
sisa uang yang perlu kita bayar adalah N − a k . Dalam kasus ini, terdapat M pilihan koin untuk
a k . Perhatikan bahwa penukaran N − a k merupakan suatu subpersoalan yang serupa dengan
persoalan awalnya. Artinya, cara yang sama untuk menyelesaikan subpersoalan dapat digunakan
sehingga strategi penyelesaian secara rekursif dapat digunakan.
Solusi Rekursif
Definisikan sebuah fungsi f (x) sebagai banyaknya koin minimum yang dibutuhkan untuk
membayar tepat x rupiah. Kita dapat mencoba-coba satu koin yang ingin kita gunakan. Jika suatu
koin a k digunakan, maka kita membutuhkan f (x − a k ) koin ditambah satu koin a k , atau dapat ditulis
f (x) = f (x − a k ) + 1. Pencarian nilai f (x − a k ) dilakukan secara rekursif, kita kembali mencoba-coba
koin yang ingin digunakan. Pilihan yang terbaik akan memberikan nilai f (x − a k ) + 1 sekecil mungkin,
sehingga kita cukup mencoba semua kemungkinan a k , dan ambil yang hasil f (x − a k ) + 1 terkecil.
Dalam solusi rekursif, kita harus menentukan base case dari f (x). Kasus terkecilnya adalah
f (0), yang artinya kita hendak membayar 0 rupiah. Membayar 0 rupiah tidak membutuhkan satu
pun koin, sehingga f (0) = 0. Secara matematis, hubungan rekursif ini dituliskan:

x = 0
 0,
f (x) =
min f (x − a k ) + 1, x > 0
 1≤k≤M
a k ≤x
Kita implementasikan f (x) sebagai fungsi SOLVE (x) pada Algoritma 27.
Algoritma 27 Penyelesaian Coin Change secara rekursi.
function SOLVE (x)
2:
if (x = 0) then
3:
return 0
4:
end if
1:
5:
6:
7:
8:
9:
10:
11:
12:
best ← ∞
for k ← 1, M do
if (a k ≤ x) then
best ← min(best, SOLVE (x − a k ) + 1)
end if
end for
return best
end function
63