Catatan Kuliah: Pemrograman Dinamis

Pendahuluan

• Assalamualaikum warahmatullahi wabarakatuh
• Materi: Strategi Algoritmik dan Pemrograman
• Fokus: Berpikir Komputasional dan Pemrograman Dinamis

Pemrograman Dinamis (Dynamic Programming)

• Digunakan untuk menyelesaikan permasalahan optimasi (mencari nilai terbesar atau terkecil).
• Mempertimbangkan beberapa kemungkinan langkah yang dapat mempengaruhi langkah selanjutnya.
• Teknik greedy tidak selalu menghasilkan solusi optimal.

Dua Unsur Utama dalam DP:

1. Optimasi:

   • Mencari nilai terkecil atau terbesar melalui pilihan yang tepat.
   • Perbedaan: Pilihan terbaik saat ini tidak selalu pilihan terbaik secara keseluruhan.

2. Sub-Permasalahan:

   • Nilai optimal biasanya merupakan kombinasi dari sub-permasalahan yang lebih kecil.
   • Sub-permasalahan sering memiliki overlap.
   • Menghindari perulangan dengan teknik memoisasi (menyimpan hasil perhitungan).

Contoh Kasus: Memanen Cabai

• Agria memanen cabai dalam bentuk kotak-kotak.
• Harus memilih jalur untuk memaksimalkan hasil panen.
• Agria mulai dari kolom kiri dan berhenti di kolom kanan, dapat bergerak ke kanan atau ke bawah.

Analisis Permasalahan:

• Pendekatan greedy tidak optimal.
• Contoh: Memulai dari nilai tertinggi tidak menghasilkan hasil terbaik.
• Metode coba semua kemungkinan akan terlalu banyak dan tidak efisien.

Pendekatan DP untuk Memecahkan Masalah:

• Menyatakan solusi sebagai kombinasi dari supermasalah yang lebih kecil.
• Menggunakan hasil dari kotak atas atau sebelah kiri untuk menghitung nilai maksimal di kotak saat ini.
• Menghindari perhitungan yang sama dengan memoisasi.

Tabel Memoisasi:

• Menghitung nilai maksimal hingga kotak tertentu dengan tabel yang menyimpan hasil.
• Contoh hasil tabel memoisasi untuk tanaman cabai:
  • Kotak paling kiri atas: 0
  • Setiap langkah menghitung nilai maksimal dari atas dan kiri.
  • Nilai terbesar pada tabel menunjukkan jumlah cabai terbanyak yang bisa dikumpulkan.

Aktivitas: Permainan Angka

• Ani dan Budi bermain angka:
  • Budi mengubah bilangan n menjadi 1 dengan langkah-langkah tertentu.
  • Pertanyaan: Tentukan langkah minimum untuk N = 25.

Pertanyaan Refleksi:

1. Dapatkah permasalahan penukaran uang diselesaikan dengan teknik pemrograman dinamis?
2. Contoh permasalahan lain dalam kehidupan yang dapat diselesaikan dengan teknik DP?
3. Perbedaan antara algoritma greedy dan pemrograman dinamis? Kelebihan dan kekurangan masing-masing?

Penutup

• Materi pemrograman dinamis dalam berpikir komputasional.
• Terima kasih, semoga bermanfaat.
• Selamat belajar dan tetap semangat!