Dynamic Programming (DP) adalah teknik pemrograman untuk menyelesaikan masalah kompleks dengan memecahnya menjadi submasalah yang lebih kecil, menyimpan hasil dari submasalah yang telah diselesaikan, dan menggunakannya kembali untuk menghindari perhitungan ulang.
Ciri-Ciri Masalah yang Cocok untuk DP
- Overlapping Subproblems: Submasalah yang sama dihitung berkali-kali.
- Optimal Substructure: Solusi dari masalah utama dapat disusun dari solusi submasalahnya.
Contoh Studi Kasus
Berikut adalah beberapa studi kasus untuk memahami penerapan Dynamic Programming di C++.
1. Fibonacci Number
Menghitung bilangan Fibonacci ke-n dengan DP.
Pendekatan Tabulasi (Bottom-Up):
#include <iostream>
#include <vector>
using namespace std;
int fibonacci(int n) {
if (n <= 1) return n;
vector<int> dp(n + 1);
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
int main() {
int n = 10;
cout << "Fibonacci ke-" << n << " adalah: " << fibonacci(n) << endl;
return 0;
}2. Knapsack Problem (0/1 Knapsack)
Diberikan daftar item dengan berat dan nilai masing-masing, tentukan nilai maksimum yang dapat dimasukkan ke dalam tas dengan kapasitas tertentu.
Pendekatan Tabulasi (Bottom-Up):
#include <iostream>
#include <vector>
using namespace std;
int knapsack(vector<int>& weights, vector<int>& values, int W) {
int n = weights.size();
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= n; i++) {
for (int w = 1; w <= W; w++) {
if (weights[i - 1] <= w) {
dp[i][w] = max(dp[i - 1][w], values[i - 1] + dp[i - 1][w - weights[i - 1]]);
} else {
dp[i][w] = dp[i - 1][w];
}
}
}
return dp[n][W];
}
int main() {
vector<int> weights = {2, 3, 4, 5};
vector<int> values = {3, 4, 5, 6};
int W = 5;
cout << "Nilai maksimum yang dapat dimasukkan: " << knapsack(weights, values, W) << endl;
return 0;
}3. Longest Common Subsequence (LCS)
Diberikan dua string, temukan panjang subsekuensi terpanjang yang sama di kedua string.
Pendekatan Tabulasi (Bottom-Up):
#include <iostream>
#include <vector>
using namespace std;
int lcs(string X, string Y) {
int m = X.size();
int n = Y.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (X[i - 1] == Y[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
int main() {
string X = "AGGTAB";
string Y = "GXTXAYB";
cout << "Panjang LCS adalah: " << lcs(X, Y) << endl;
return 0;
}4. Coin Change Problem
Diberikan sejumlah denominasi koin, tentukan jumlah minimum koin untuk mencapai nilai tertentu.
Pendekatan Tabulasi (Bottom-Up):
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, INT_MAX);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (i - coin >= 0 && dp[i - coin] != INT_MAX) {
dp[i] = min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] == INT_MAX ? -1 : dp[amount];
}
int main() {
vector<int> coins = {1, 2, 5};
int amount = 11;
cout << "Jumlah minimum koin: " << coinChange(coins, amount) << endl;
return 0;
}Kesimpulan
Dynamic Programming membantu menyelesaikan masalah kompleks dengan cara:
- Memecah masalah besar menjadi submasalah kecil.
- Menyimpan hasil submasalah dalam array (atau hashmap).
- Menghindari perhitungan ulang, sehingga lebih efisien dibanding pendekatan rekursif murni.
Jika Anda ingin penjelasan tambahan atau studi kasus lainnya, beri tahu saya! 😊
Leave a Reply