Page 42 - EMODUL INFORMATIKA XI FASE F

Agria tidak punya waktu banyak karena ia harus segera
pergi ke kampus. Oleh karena itu, ia tidak bisa memetik seluruh

cabai tersebut. Ia hanya bisa mulai dari kotak manapun di kolom
paling kiri, dan berhenti di kotak manapun di kolom paling
kanan. Agria hanya bisa bergerak ke kotak di tepat setelah

kanannya atau bawahnya. Berikut adalah salah satu dari sekian
banyak kemungkinan jalur yang dapat dilalui oleh Agria untuk

memetik cabai.
Berapakah jumlah cabai terbanyak yang bisa
dikumpulkan oleh Agria?
Jawab:

Pertama, perlu dipahami bahwa penggunaan teknik
greedy pada permasalahan ini tidak akan menghasilkan

jawaban yang benar/optimal. Dapat dilihat bahwa jika kita
menggunakan prinsip greedy, maka kita akan memilih untuk
memulai dari kolom pertama baris terakhir, dengan nilai jumlah

cabai terbesar, yaitu 20. Namun, jika kita memulai dari sini,
maka tidak ada pilihan lain untuk langkah-langkah selanjutnya,

selain bergerak terus ke kanan. Maka nilai total cabai yang akan
didapatkan adalah = 20 + 5 + 1 + 0 + 0 = 26. Jelas bahwa ada
pilihan-pilihan jalur lain yang akan menghasilkan total nilai
cabai > 26, misalnya langkah sebagai berikut akan

menghasilkan jumlah total cabai = 0 + 10 + 2 + 10 + 10 + 5 = 37.

42