Lewati ke konten utama
Numekara
Konsultasi GratisKontak

K1 · Modul 14

Pemrograman dinamis

48 langkah singkat, dari mudah sampai tantangan.

  1. Level 1

    Kenal

  2. Level 2

    Paham

  3. Level 3

    Terapkan

  4. Level 4

    Tantangan

  5. Level 5

    Pendalaman

Intinya

  • Pemrograman dinamis = rekursi dengan submasalah tumpang-tindih yang setiap jawabannya disimpan sekali.
  • Resepnya: definisikan submasalah dalam satu kalimat, tulis rekurensinya, tentukan urutan pengisian, hitung waktu (banyak submasalah × kerja per submasalah), lalu rekonstruksi solusinya.
  • Memo (atas ke bawah) mudah ditulis; tabel (bawah ke atas) bebas batas rekursi dan sering bisa diperkecil menjadi satu baris.
  • Knapsack 0/1 O(n·C) bersifat pseudo-polinomial: biayanya tumbuh dengan nilai kapasitas, bukan banyak digitnya.

Sebelum mulai

±4–5 jam.

Modul ini memakai materi di bawah. Belum yakin? Ulas dulu bagian yang disebut.

Hasil belajar: mengenali submasalah tumpang-tindih dan substruktur optimal; menurunkan rekurensi dari definisi submasalah; mengubah rekursi menjadi memo lalu tabel; membuktikan rekurensi dengan induksi dan menganalisis waktu serta ruangnya; merekonstruksi solusi dengan pemecah seri; serta menyelesaikan knapsack 0/1, kembalian koin, jarak edit, dan subbarisan naik terpanjang.

Proyek: Kurir Makmur langkah 14: muat_motor (knapsack 0/1 dengan pemecah seri kontrak), kembalian, jarak_edit, dan koreksi salah ketik nama produk Warung Makmur (kontrak Proyek Kurir §3).

Istilah di modul ini (29)

Ketuk istilah untuk melihat penjelasannya. Di materi, istilah bergaris titik membuka kartu yang sama. Semua istilah course

Bahan modul

Semua kode, latihan, dan data modul ini dalam satu zip, untuk dijalankan di laptop atau Google Colab.

  • 29 contoh kode
  • 9 berkas latihan + tes
  • 1 berkas data
Semua data course (data-k1.zip) Cara menjalankan di laptop
Lihat isi zip
  • BACA-DULU.txt
  • kurir_dasar.py
  • contoh_k1_14_43.py
  • contoh_k1_14_69.py
  • contoh_k1_14_101.py
  • contoh_k1_14_154.py
  • contoh_k1_14_189.py
  • contoh_k1_14_292.py
  • contoh_k1_14_328.py
  • contoh_k1_14_363.py
  • contoh_k1_14_400.py
  • contoh_k1_14_533.py
  • contoh_k1_14_572.py
  • contoh_k1_14_657.py
  • contoh_k1_14_703.py
  • contoh_k1_14_739.py
  • contoh_k1_14_767.py
  • contoh_k1_14_794.py
  • contoh_k1_14_820.py
  • contoh_k1_14_989.py
  • contoh_k1_14_1118.py
  • contoh_k1_14_1146.py
  • contoh_k1_14_1171.py
  • contoh_k1_14_1331.py
  • contoh_k1_14_1386.py
  • contoh_k1_14_1420.py
  • contoh_k1_14_1457.py
  • contoh_k1_14_1496.py
  • contoh_k1_14_2283.py
  • contoh_k1_14_2326.py
  • contoh_k1_14_2383.py
  • test_k1_14_1.py
  • test_k1_14_4.py
  • test_k1_14_2.py
  • test_k1_14_3.py
  • test_k1_14_5.py
  • test_k1_14_6.py
  • test_k1_14_7.py
  • test_k1_14_8.py
  • test_k1_14_9.py
  • peta.json