Mengapa Program Dinamis (DP) Begitu Revolusioner?
Dalam dunia ilmu komputer dan optimisasi, seringkali kita dihadapkan pada masalah kompleks yang, jika dipecahkan dengan cara konvensional (seperti rekursi murni), akan membutuhkan waktu dan sumber daya komputasi yang sangat besar. Di sinilah Pemrograman Dinamis (Dynamic Programming - DP) hadir sebagai solusi yang elegan dan efisien.
Pemrograman Dinamis adalah sebuah teknik algoritmik untuk menyelesaikan masalah kompleks dengan memecahnya menjadi sub-masalah yang lebih kecil, menyelesaikan setiap sub-masalah hanya sekali, dan menyimpan solusi tersebut untuk digunakan kembali. Kunci dari DP adalah menghindari perhitungan berulang (Overlapping Subproblems) dan memastikan bahwa solusi optimal global dapat ditemukan dari solusi optimal lokal (Optimal Substructure).
Baca juga:Menguji Pengalaman Pengguna Solusi Cerdas dengan Robot Tester
Pilar Utama Pemrograman Dinamis
Sebuah masalah hanya dapat dipecahkan secara efisien menggunakan DP jika memenuhi dua kriteria utama:
1. Struktur Optimal (Optimal Substructure)
Ini berarti solusi optimal dari masalah yang lebih besar dapat dibangun dari solusi optimal sub-masalah yang lebih kecil. Misalnya, rute terpendek dari Kota A ke Kota D harus mencakup rute terpendek dari A ke salah satu kota perantara.
2. Sub-Masalah Berulang (Overlapping Subproblems)
Ini adalah ciri khas DP. Artinya, algoritma rekursif alami akan memanggil fungsi yang sama dengan parameter yang sama berulang kali. DP mengatasi ini dengan teknik Memoization (pendekatan Top-Down, menyimpan hasil di tabel saat dihitung) atau Tabulation (pendekatan Bottom-Up, mengisi tabel dari kasus dasar).
Contoh Soal 1: Deret Fibonacci (Ilustrasi Sub-Masalah Berulang)
Deret Fibonacci adalah barisan bilangan di mana setiap bilangan (kecuali dua yang pertama) merupakan penjumlahan dari dua bilangan sebelumnya.
$$F(n) = F(n-1) + F(n-2)$$
dengan $F(0) = 0$ dan $F(1) = 1$.
Masalah: Hitung nilai suku ke-5 dari Deret Fibonacci, $F(5)$.
A. Pendekatan Rekursif Konvensional (Inefisien)
Jika kita menghitung $F(5)$ menggunakan rekursi murni:
$$F(5) = F(4) + F(3)$$
$$F(5) = (F(3) + F(2)) + (F(2) + F(1))$$
$$F(5) = ((F(2) + F(1)) + (F(1) + F(0))) + ((F(1) + F(0)) + 1)$$
Perhatikan: $F(3)$ dihitung dua kali, $F(2)$ dihitung dua kali, dan $F(1)$ dihitung tiga kali. Untuk $F(n)$ yang besar, jumlah perhitungan berulang akan meningkat secara eksponensial ($O(2^n)$), membuat program sangat lambat.
B. Pendekatan Pemrograman Dinamis (Tabulation / Bottom-Up)
DP menyelesaikan masalah ini dengan mengisi tabel dari kasus dasar:
- Inisialisasi Kasus Dasar:
- $F[0] = 0$
- $F[1] = 1$
- Iterasi (Menghindari Pengulangan): Hitung dari $i=2$ hingga $n=5$.
- $F[2] = F[1] + F[0] = 1 + 0 = 1$
- $F[3] = F[2] + F[1] = 1 + 1 = 2$
- $F[4] = F[3] + F[2] = 2 + 1 = 3$
- $F[5] = F[4] + F[3] = 3 + 2 = 5$
| Suku (n) | Perhitungan | F(n) |
| 0 | - | 0 |
| 1 | - | 1 |
| 2 | $F(1) + F(0)$ | 1 |
| 3 | $F(2) + F(1)$ | 2 |
| 4 | $F(3) + F(2)$ | 3 |
| 5 | $F(4) + F(3)$ | 5 |
Kesimpulan DP vs Rekursi:
Dengan DP, kita hanya melakukan satu kali penjumlahan untuk setiap suku (total 4 penjumlahan), sementara rekursi konvensional memerlukan banyak perhitungan yang sama. Kompleksitas DP hanya $O(n)$, jauh lebih efisien.
Contoh Soal 2: Masalah Ransel (Knapsack Problem)
Masalah Ransel 0/1 (setiap barang hanya boleh diambil 0 atau 1 kali) adalah masalah optimisasi klasik yang ideal untuk DP.
Masalah:
Seorang pendaki memiliki ransel dengan kapasitas maksimum 5 kg. Tersedia 3 jenis barang dengan berat dan nilai sebagai berikut. Bagaimana cara pendaki memilih barang agar total nilai maksimum tanpa melebihi kapasitas ransel?
| Barang (i) | Berat (Wi, kg) | Nilai (Vi) |
| 1 | 2 | 20 |
| 2 | 3 | 45 |
| 3 | 4 | 75 |
Formulasi DP (Bottom-Up / Tabulation)
Kita akan membuat tabel $DP[i][w]$ yang merepresentasikan nilai maksimum yang dapat dicapai dengan menggunakan $i$ barang pertama dengan kapasitas ransel $w$.
Persamaan Rekursi Dasar:
$$DP[i][w] = \begin{cases} DP[i-1][w] & \text{jika } W_i > w \text{ (Barang } i \text{ tidak muat)} \\ \max(DP[i-1][w], V_i + DP[i-1][w - W_i]) & \text{jika } W_i \le w \text{ (Pilih antara tidak ambil atau ambil barang } i \text{)} \end{cases}$$
Tabel $DP[i][w]$ akan berukuran $4 \times 6$ (4 baris untuk barang 0 hingga 3, dan 6 kolom untuk kapasitas 0 hingga 5).
| DP[i][w] | w=0 | w=1 | w=2 | w=3 | w=4 | w=5 |
| i=0 (Dasar) | 0 | 0 | 0 | 0 | 0 | 0 |
| i=1 (B1, W=2, V=20) | 0 | 0 | 20 | 20 | 20 | 20 |
| i=2 (B2, W=3, V=45) | 0 | 0 | 20 | 45 | 45 | 65 |
| i=3 (B3, W=4, V=75) | 0 | 0 | 20 | 45 | 75 | 75 |
Langkah Pengisian Tabel:
Baris $i=1$ (Barang 1: W=2, V=20):
- $w=0, 1$: $W_1 > w$, $DP[1][w] = DP[0][w] = 0$.
- $w=2$: $W_1 \le w$. $\max(DP[0][2], 20 + DP[0][2-2]) = \max(0, 20+0) = 20$.
- $w=3, 4, 5$: $DP[1][w]$ akan mengikuti nilai $DP[1][2]=20$ karena tidak ada barang lain yang bisa dimasukkan.
Baris $i=2$ (Barang 2: W=3, V=45):
- $w=0, 1, 2$: $W_2 > w$. $DP[2][w] = DP[1][w]$. (Contoh: $DP[2][2]=20$)
- $w=3$: $W_2 \le w$. $\max(DP[1][3], 45 + DP[1][3-3])$. $\max(20, 45+0) = \mathbf{45}$.
- $w=4$: $W_2 \le w$. $\max(DP[1][4], 45 + DP[1][4-3])$. $\max(20, 45+0) = \mathbf{45}$.
- $w=5$: $W_2 \le w$. $\max(DP[1][5], 45 + DP[1][5-3])$. $\max(20, 45+20) = \mathbf{65}$.
Baris $i=3$ (Barang 3: W=4, V=75):
- $w=0, 1, 2, 3$: $W_3 > w$. $DP[3][w] = DP[2][w]$. (Contoh: $DP[3][3]=45$)
- $w=4$: $W_3 \le w$. $\max(DP[2][4], 75 + DP[2][4-4])$. $\max(45, 75+0) = \mathbf{75}$.
- $w=5$: $W_3 \le w$. $\max(DP[2][5], 75 + DP[2][5-4])$. $\max(65, 75+0) = \mathbf{75}$.
Kesimpulan Solusi Optimal:
Nilai maksimum yang bisa dicapai dengan kapasitas 5 kg adalah $\mathbf{75}$. Ini dicapai dengan melihat $DP[3][5] = 75$.
- Untuk mendapatkan 75 di $DP[3][5]$, kita harus mengambil Barang 3 (Nilai 75).
- Sisa kapasitas: $5 - 4 = 1$ kg.
- Kembali ke $i=2$ dengan sisa $w=1$. $DP[2][1]=0$. Artinya, tidak ada barang dari $i=1, 2$ yang bisa diambil lagi.
Kombinasi Optimal: Hanya mengambil Barang 3 (Berat 4 kg, Nilai 75).
Baca juga:Wakil Rektor Hadiri Pisah Sambut Kapolda Baru, Teknokrat Perkuat Sinergi dengan Polda Lampung
Perbedaan Mendasar: DP vs Greedy
Seringkali Pemrograman Dinamis dikontraskan dengan Algoritma Greedy.
| Fitur | Pemrograman Dinamis (DP) | Algoritma Greedy |
| Fokus Keputusan | Optimalisasi Solusi Global (Mempertimbangkan masa depan) | Optimalisasi Keputusan Lokal Saat Ini (Tidak melihat ke belakang/depan) |
| Optimalisasi | Menggunakan Struktur Optimal dan Sub-masalah Berulang | Tidak menjamin solusi optimal global |
| Penerapan | Knapsack 0/1, Rute Terpendek All-Pairs, Longest Common Subsequence | Masalah Penukaran Koin (tertentu), Rute Terpendek Single-Source (Dijkstra) |
Mengapa Greedy Gagal di Knapsack?
Jika kita menggunakan strategi Greedy (misalnya, ambil barang dengan nilai/berat tertinggi), kita mungkin akan mengambil Barang 3 (75/4) terlebih dahulu, menyisakan 1 kg dan nilai total 75. Jika kita Greedy mengambil Barang 2 (45/3) terlebih dahulu, kita tidak bisa mengambil Barang 3 dan nilai total hanya 45 (gagal). Greedy bisa salah memilih. DP, dengan mengevaluasi semua kemungkinan solusi sub-masalah, selalu menjamin solusi optimal.
Penutup
Pemrograman Dinamis adalah alat yang sangat ampuh dalam menyelesaikan kelas masalah optimisasi yang rumit di mana solusi optimal tergantung pada solusi optimal sub-masalah yang berulang. Dengan menguasai konsep dasar Optimal Substructure dan Overlapping Subproblems yang diilustrasikan melalui contoh klasik seperti Deret Fibonacci dan Knapsack Problem, Anda akan memiliki fondasi yang kuat dalam berpikir secara algoritmik dan efisien.
Penulis:Zaskia amelia
