Apa Itu Pemrograman Dinamis? Ini Pengertian dan Contohnya - Halo ders apa kabar? pembahasan kali ini kita akan ulas pemrograman dinamis. Kira-kira kalian udah pada kenal belum nih apa itu pemrograman dimamis. Kalo belum maka tepat banget nih kamu baca artikel ini, karena kita akan coba ulas lebih dalam dan kita caritahu contoh pemrograman dinamis agar kalian bisa paham betul.

Jadi secara singkat jika pemrograman dinamis adalah teknik ampuh yang membedah permasalahan kompleks menjadi sub-masalah yang lebih mudah di cerna. Yasudah tanpa berlama-lama kita langsung ulas aja yuk, karekteristik pemrograman dinamis dan pembahasan lebih lengkapnya dalam artikel ini.

Pengertian Pemrograman Dinamis

Pemrograman dinamis (PD) adalah teknik optimasi yang digunakan untuk memecahkan masalah dengan struktur tertentu. PD bekerja dengan memecah masalah besar menjadi sub-masalah yang lebih kecil dan saling terkait. Hebatnya, solusi dari sub-masalah ini di simpan untuk digunakan kembali saat dibutuhkan, sehingga kita tidak perlu menghitung ulang hal yang sama berkali-kali. Pendekatan ini membuat PD sangat efisien untuk masalah-masalah yang memiliki properti berikut:

• ** overlapping subproblems :** atau dikenal sebagai sub-masalah yang tumpang tindih atau masalah besar dapat di bagi menjadi sub-masalah yang lebih kecil, dimana beberapa sub-masalah ini mungkin identik atau serupa.
• optimal substructure : Solusi optimal untuk masalah keseluruhan dapat dibangun dari solusi optimal sub-masalahnya.

Baca Juga: Beasiswa Coding Gratis DevHandal Sponsor Alibaba Cloud!

Kenapa PD Begitu Hebat? - Keunggulan dan Kelebihannya

PD menawarkan segudang keuntungan yang membuat programmer jatuh cinta. Mari kita lihat beberapa alasan mengapa PD menjadi senjata ampuh dalam gudang programmer:

• Efisiensi: PD menghindari perhitungan berulang pada sub-masalah yang sama. Ini berdampak signifikan pada kecepatan program, terutama untuk masalah kompleks.
• Kesederhanaan: PD seringkali membuat kode program lebih mudah di pahami dan di pelihara. Memecah masalah menjadi sub-masalah yang lebih kecil membuat logika program lebih jelas.
• Kemampuan memecahkan masalah kompleks: PD dapat menangani masalah yang sulit di selesaikan dengan pendekatan rekursif biasa. Dengan memecah masalah menjadi sub-masalah, PD menawarkan solusi yang lebih efisien.

Memori Memoization

Salah satu konsep penting dalam Pemrograman Dinamis adalah memoization (penghafalan). Memoization adalah teknik menyimpan hasil perhitungan sub-masalah untuk digunakan kembali di masa mendatang.

Dengan memoization, program tidak perlu menghitung ulang sub-masalah yang sudah pernah di hitung. Ini seperti memiliki catatan kecil yang berisi hasil perhitungan sebelumnya, sehingga kita tidak perlu repot-repot menghitung ulang hal yang sama.

Memoization biasanya di implementasikan dengan menggunakan tabel atau array untuk menyimpan hasil perhitungan sub-masalah.

Contoh 1: Fibonnaci dengan PD - Lebih Cepat dari Kelinci!

Deret Fibonacci adalah barisan angka dimana setiap angka adalah hasil penjumlahan dua angka sebelumnya. Deret ini terkenal karena kemunculannya di berbagai bidang, mulai dari biologi hingga keuangan.

Perhitungan deret Fibonacci secara rekursif bisa menjadi boros dalam hal sumber daya komputasi. Ini karena fungsi rekursif untuk Fibonacci seringkali menghitung sub-masalah yang sama berulang kali.

PD hadir sebagai penyelamat! Dengan memoization, kita dapat menyimpan hasil perhitungan sub-masalah sebelumnya, sehingga program tidak perlu menghitung ulang hal yang sama.

Berikut contoh perhitungan Fibonacci menggunakan PD dalam bahasa Python:

def fibonacci (n, memo={}):
  if n == 0 or n == 1:
    return n
  if n in memo:
    return m3m0 [n]
  else:
    memo
		```
		
## Contoh 2:  Knapsack Problem -  Memilih Barang yang Tepat untuk Petualangan

Bayangkan Anda sedang berpetualang di hutan dan perlu membawa barang sebanyak mungkin dengan ruang tas yang terbatas.  Anda memiliki berbagai macam barang dengan berat dan nilainya masing-masing.  

Masalahnya, bagaimana memilih kombinasi barang yang tepat agar nilainya maksimal,  tanpa melebihi batas kapasitas tas?  

Masalah ini dikenal sebagai "knapsack problem".  PD  dapat membantu memecahkan masalah ini dengan cara yang efisien.

Berikut contoh penyelesaian *knapsack* problem menggunakan PD dalam bahasa Python:

```python
def knap sack(items, max_weight):
  table = [[0 for x in range(max_weight + 1)] for y in range(len(items) + 1)]

  for i in range (len(items) + 1):
    for w in range(max_weight + 1):
      if i == 0 or w == 0:
        table[i][w] = 0
      elif items[i - 1].weight <= w:
        table[i][w] = max(table[i - 1][w], table[i - 1][w - items[i - 1].weight] + items[i - 1].value)
      else:
        table[i][w] = table[i - 1][w]

  return table[len(items)][max_weight]

Contoh 3: Coin Change Problem - Menemukan Kombinasi Uang Kembalian

Pernahkah Anda kesal karena tidak memiliki uang receh untuk kembalian? Dengan PD, Anda dapat menemukan kombinasi uang receh yang tepat untuk memberikan kembalian kepada pelanggan dengan cara yang efisien.

Berikut contoh penyelesaian coin change problem menggunakan PD dalam bahasa Python:

def coin_ch4nge (coins, amount):
  table = [0 for x in range (amount + 1)]

  for i in range(len(coins)):
    for j in range(amount + 1):
      if coins[i] <= j:
        table[j] = min(table[j], table[j - coins[i]] + 1)

  return table[amount]

Baca Juga: 8+ Manfaat Cloud Computing, Ikut Sertifikasi Internasional

Kesimpulan

Pemrograman dinamis (PD) adalah teknik ampuh yang membantu programmer memecahkan masalah kompleks dengan cara yang efisien. PD bekerja dengan memecah masalah besar menjadi sub-masalah yang lebih kecil dan saling terkait. Solusi dari sub-masalah ini disimpan untuk digunakan kembali saat dibutuhkan, sehingga program tidak perlu menghitung ulang hal yang sama berkali-kali.

PD menawarkan banyak keuntungan, termasuk efisiensi, kesederhanaan, dan kemampuan memecahkan masalah kompleks. PD cocok untuk masalah yang dapat dibagi menjadi sub-masalah yang lebih kecil dan memiliki solusi optimal.

Memoization adalah konsep penting dalam PD yang membantu meningkatkan efisiensi program. Dengan memoization, program dapat menyimpan hasil perhitungan sub-masalah sebelumnya, sehingga tidak perlu menghitung ulang hal yang sama.

Pemrograman Dinamis telah terbukti menjadi alat yang berharga dalam berbagai bidang, termasuk pemrograman komputer, operasi riset, dan ilmu komputer. Dengan memahami konsep dan teknik PD, programmer dapat mengembangkan program yang lebih efisien dan efektif untuk memecahkan berbagai masalah kompleks.

Ingatlah: PD adalah teknik yang kuat, tetapi tidak selalu mudah untuk diterapkan. Membutuhkan pemahaman yang baik tentang masalah dan struktur datanya untuk menggunakan PD secara efektif.

Referensi

• https://en.wikipedia.org/wiki/Dynamic_programming
• https://www.coursera.org/courses?query=dynamic%20programming
• https://www.geeksforgeeks.org/dynamic-programming/