Creator Media

Algoritma Dynamic Programming

Dynamic programming merupakan penyelesaian masalah optimasi yang dikembangkan oleh Richar Bellman pada tahun 1952. Metode dynamic programming adalah pendekatan umum yang muncul sebagai alat yang berguna di banyak bidang Research Operation (RO). Pada dasarnya, metode ini diterapkan pada masalah optimasi yang melibatkan urutan keputusan, solusi optimal dari masalah yang asli dapat ditemukan dari solusi optimal subproblem (Kellerer, Pferschy dan Pisinger, 2004).

Definisi lain, dynamic programming adalah metode pemecahan dengan menguraikan solusi menjadi serangkaian langkah atau langkah-langkah sehingga solusi dari masalah dapat dilihat dari serangkaian keputusan yang saling berhubungan (Sampurno, Sugiharti dan Alamsyah, 2018). Jadi dapat disimpulkan bahwa dynamic programming adalah metode pemecahan masalah dengan menguraikan solusi menjadi beberapa tahapan atau langkah-langkah sehingga solusi optimalnya dapat ditemukan dari rangkaian keputusan yang saling berkaitan. Algoritma dynamic programming dalam menyelesaikan masalah integer knapsack berdasarkan Pan dan Zhang (2018) mempunyai kompleksitas waktu O nW( ) , dimana W adalah koefisien dari kapasitasnya.

Algoritma dynamic programming menggunakan teknik bottom-up. Ada tiga elemen dasar dalam teknik bottom-up berdasarkan Kwarteng dan Asante (2017) yaitu :

1. 1. Substructure
      Mengurai masalah yang ada menjadi masalah yang lebih kecil dan mulai dengan permasalahan yang paling kecil.
   2. Struktur tabel
      Simpan jawaban (hasil) ke dalam tabel.
   3. Perhitungan bottom-up

Prinsipnya adalah menggunakan tabel untuk menggabungkan solusi dari masalah lebih kecil yang didapatkan, kemudian untuk menyelesaikan masalah yang lebih besar, dan diproses sampai akhir hingga mendapat solusi optimum untuk menyelesaikan masalah.

Pembahasan lainnya :

• 1. Konsep Dasar Stack
  2. Jenis-Jenis Binary Tree
  3. Strategi Algoritma Greedy
  4. Pengertian Knapsack Problem
  5. Contoh Soal Knapsack Problem
  6. Elemen Elemen Algoritma Greedy
  7. Karakteristik Algoritma Brute Force
  8. Keunggulan Bahasa Pemrograman Java
  9. Pengertian Logaritma dan Sifat-Sifatnya
  10. Efisiensi Algoritma Ditinjau dari 2 Dua Hal
  11. Algoritma Boyer Moore untuk String Matching
  12. Penyelesaian Knapsack Problem dengan Kriteria Greedy