Page 44 - EMODUL INFORMATIKA XI FASE F
P. 44
Menggunakan prinsip DP, yang perlu kita lakukan adalah
pertama-tama menyatakan solusi/penyelesaian dari
permasalah an awal sebagai kombinasi dari sub-permasalahan
yang lebih kecil. Dalam hal ini, kita dapat membuat argumentasi
bahwa nilai jumlah cabai terbanyak yang bisa kita kumpulkan
sampai dengan suatu kotak tertentu (di manapun kolomnya)
tergantung dari nilai terbaik jumlah cabai sampai dengan kotak
di atasnya, atau kotak di sebelah kirinya (jika ada), dan tinggal
kita jumlahkan saja dengan nilai banyaknya cabai di kotak akhir
tersebut. Hal ini, tentunya karena kita hanya bisa bergerak ke
kanan atau ke bawah saja. Misalnya, pada Gambar 2.12 ini:
Nilai terbaik yang bisa kita dapatkan akan berakhir pada
kotak berwarna hitam, dapat dihitung dengan cara menghitung
nilai terbaik yang didapatkan sampai dengan kotak merah
(misalkan nilainya = A), dan sampai dengan kotak warna biru
(misalkan nilainya = B). Maka, untuk mendapatkan nilai terbaik
sampai dengan kotak warna hitam, kita hanya mencari,
manakah jumlah yang tertinggi antara nilai A dan B, kemudian
nilai tersebut dijumlahkan dengan nilai C.
Proses di atas mengubah permasalahan ini menjadi
bersifat rekursif, dimana kita bisa menggunakan hasil
perhitungan pada kotak-kotak sebelumnya untuk menghitung
nilai terbaik pada kotak-kotak selanjutnya (yang berada di
posisi lebih ke kanan atau ke bawah), sehingga dengan cara ini,
44
