30
3. Menyusun solusi optimal
untuk problem dengan
menggunakan solusi-solusi optimal
untuk subproblem-subproblem yang telah didapatkan.
Subproblem-subproblem yang
didapatkan
disini
akan
dipecahkan
dengan
cara
membaginya
menjadi
beberapa
subsubproblem, dan
seterusnya
sampai
didapatkan
subproblem-
subproblem yang
cukup
sederhana
untuk
dapat
diselesaikan
secara
trivial.
Dalam
pelaksanaannya, metode
dynamic
programming
ini
akan
menjumpai
subproblem-subproblem
yang sama
lebih dari
satu kali
(overlapping
subproblems)
dalam
proses
pencarian solusi
secara
rekursif,
sehingga
pendekatan
naive
untuk
menyelesaikan masalah
akan
kurang
efisien
(karena
harus
menghitung
ulang
solusi
optimal
dari
subproblem-subproblem
yang
telah
diselesaikan).
Karena
itu
metode
dynamic
programming
ini
pada
umumnya
menggunakan pendekatan
memoization,
yaitu
menyimpan solusi-solusi optimal
yang
sudah
diperoleh ke
dalam
suatu
tabel
dan
mengambilnya kembali
dari
tabel
pada
saat
solusi
tersebut
dibutuhkan
lagi
kemudian,
sehingga menghemat waktu yang dibutuhkan untuk menghitung solusi dari subproblem tersebut.
Sehingga
dapat
disimpulkan bahwa
metode
dynamic
programming
ini
memanfaatkan
optimal
substructure
(substruktur
optimal),
overlapping
subproblems
(subproblem-subproblem
yang berulang), dan memoization (menyimpan solusi dari subproblem dalam suatu tabel).
Dalam prakteknya,
terdapat dua
macam pendekatan pada
implementasi
metode
ini,
yaitu
pendekatan top-down
dan
pendekatan bottom-up.
Pada
pendekatan top-down,
problem
yang ada
dibagi
menjadi
subproblem-subproblem,
yang
kemudian
diselesaikan
dan
hasilnya
disimpan
pada
tabel
(memoization),
sehingga
dapat
digunakan
kembali
jika
dibutuhkan. Sedangkan
pada
pendekatan bottom-up,
semua
subproblem
yang
mungkin
diperlukan
akan
diselesaikan terlebih
dahulu, dan kemudian digunakan untuk menyusun jawaban dari suatu problem yang lebih besar.
 |