Algoritma Greedy dalam Pemrograman C++
Algoritma greedy adalah pendekatan sederhana untuk memecahkan masalah optimisasi dengan memilih pilihan terbaik saat ini, tanpa mempertimbangkan konsekuensi masa depan. Ide dasar algoritma greedy adalah untuk membangun solusi optimal secara bertahap dengan memilih pilihan terbaik yang tersedia pada setiap langkah.
Cara Kerja Algoritma Greedy
Algoritma greedy bekerja dengan:
- Memilih pilihan terbaik saat ini: Pada setiap langkah, algoritma memilih pilihan yang tampak paling optimal pada saat itu, tanpa mempertimbangkan konsekuensi di masa depan.
- Membangun solusi secara bertahap: Algoritma greedy membangun solusi optimal secara bertahap dengan menambahkan pilihan terbaik yang tersedia pada setiap langkah ke solusi yang sedang dibangun.
- Tidak kembali ke pilihan sebelumnya: Algoritma greedy tidak kembali ke pilihan sebelumnya, meskipun pilihan tersebut mungkin lebih baik dalam konteks yang lebih luas.
Contoh Penerapan Algoritma Greedy
Salah satu contoh penerapan algoritma greedy adalah algoritma Coin Change. Algoritma ini bertujuan untuk mencari jumlah koin terkecil yang diperlukan untuk menjumlahkan sejumlah uang tertentu.
Contoh Kode C++ untuk Algoritma Coin Change
#include
#include
#include
using namespace std;
int minCoins(vector &coins, int amount) {
sort(coins.begin(), coins.end(), greater()); // Urutkan koin dari terbesar ke terkecil
int count = 0;
for (int i = 0; i < coins.size(); i++) {
while (amount >= coins[i]) {
amount -= coins[i];
count++;
}
}
return count;
}
int main() {
vector coins = {1, 5, 10, 25};
int amount = 41;
cout << "Jumlah koin minimal: " << minCoins(coins, amount) << endl; // Output: Jumlah koin minimal: 4
return 0;
}
Keuntungan dan Kekurangan Algoritma Greedy
Keuntungan:
- Sederhana dan mudah diterapkan: Algoritma greedy mudah dipahami dan diterapkan.
- Efisien waktu: Algoritma greedy biasanya lebih efisien daripada algoritma lainnya, terutama untuk masalah besar.
Kekurangan:
- Tidak selalu menghasilkan solusi optimal: Algoritma greedy tidak selalu menghasilkan solusi optimal.
- Tidak semua masalah dapat diselesaikan dengan algoritma greedy: Algoritma greedy hanya cocok untuk masalah tertentu.
Kapan Menggunakan Algoritma Greedy
Algoritma greedy dapat digunakan untuk memecahkan berbagai masalah optimisasi, termasuk:
- Algoritma Coin Change
- Algoritma Huffman Coding
- Algoritma Dijkstra's Shortest Path
- Algoritma Kruskal's Minimum Spanning Tree
Kesimpulan
Algoritma greedy adalah alat yang ampuh untuk memecahkan masalah optimisasi. Meskipun tidak selalu menghasilkan solusi optimal, algoritma greedy menawarkan cara sederhana dan efisien untuk menemukan solusi yang baik.