Karena Brute Force memeriksa semua kemungkinan jawaban maka dalam menyelesaikan masalah yang mempunyai kemungkinan yang sangat banyak algoritma ini sangat menguras waktu.
Misal: Masalah kombinasi 3 digit angka pada password. Algoritma Brute Force akan mencoba semua kemungkinan angka dari 000, 001, 002, 003, 004 dan seterusnya sampai ditemukan kombinasi angka password yang benar. Kaena tiap digit mempunyai kemungkinan 0-9 (10 kemungkinan) maka untuk tiga digit didapat 10x10x10 = 1000 kombinasi yang mungkin.
Coba → periksa → jika salah, lanjut → jika benar, berhenti.
Algoritma Greedy dalam konteks yang lebih luas mengenai strategi optimasi berpikir komputasional mencakup beberapa poin kunci sebagai berikut:
Algoritma Greedy didefinisikan sebagai metode penyelesaian masalah yang selalu memilih keputusan terbaik pada setiap langkah individu, dengan harapan bahwa rangkaian keputusan kecil tersebut akan menghasilkan solusi terbaik secara keseluruhan atau global optimum,. Secara harfiah, istilah greedy berarti "rakus" atau "serakah" karena algoritma ini hanya mengambil keuntungan terbesar yang tersedia saat itu tanpa mempertimbangkan konsekuensi jangka panjang,.
2. Prinsip Kerja Greedy dalam Konteks Optimasi
Dalam spektrum berpikir komputasional Greedy merupakan salah satu teknik untuk menyelesaikan masalah optimasi, yaitu mencari cara terbaik untuk memecahkan masalah yang memiliki banyak kemungkinan penyelesaian.
Prinsip utamanya adalah:
Lokal Optimal: Membuat keputusan yang paling menguntungkan pada setiap langkah spesifik.Tanpa Menengok ke Belakang (No Backtracking): Pilihan yang sudah diambil bersifat final dan tidak dapat diubah atau dibatalkan di kemudian hari,,.
Penyederhanaan Langkah: Algoritma ini digunakan untuk menyederhanakan proses penyelesaian masalah dengan hanya fokus pada satu pilihan terbaik setiap kali menemukan persimpangan keputusan.
3. Peran algoritma Greedy
Greedy diposisikan sebagai alternatif dari teknik lain seperti: Brute Force:
Berbeda dengan Brute Force yang mencoba semua kemungkinan (sehingga tidak efisien untuk masalah besar), Greedy jauh lebih cepat karena hanya memilih satu jalur terbaik di setiap langkah,.
Dynamic Programming (DP):
Jika Greedy mengambil keputusan instan tanpa melihat masa depan, DP memecah masalah menjadi sub-masalah dan menyimpan hasilnya untuk menjamin solusi optimal global,
Linear Programming (LP):
Greedy adalah pendekatan prosedural, sementara LP adalah pemodelan matematika menggunakan fungsi linier dan batasan tertentu untuk optimasi,
4. Efisiensi dan Jaminan Solusi
Secara teknis, algoritma Greedy dikenal sangat efisien dengan kompleksitas waktu yang kecil dan penggunaan memori yang minimal,. Namun, Greedy tidak selalu menjamin solusi optimal global, Keputusan terbaik di awal terkadang justru bisa menghalangi tercapainya solusi terbaik di akhir, seperti yang terlihat pada kasus tertentu dalam masalah koin atau masalah tas (0/1 Knapsack)
Kelebihan Algoritma Greedy dalam konteks strategi optimasi berpikir komputasional dapat dirangkum ke dalam beberapa poin utama berikut:
Kecepatan dan Efisiensi Waktu: Keunggulan utama algoritma Greedy adalah kecepatannya yang jauh lebih singkat dibandingkan metode lain seperti Brute Force. Hal ini dikarenakan Greedy hanya memilih satu pilihan terbaik di setiap langkah tanpa harus mencoba semua kemungkinan kombinasi. Kompleksitas waktunya biasanya sangat kecil, sering kali berada pada rentang O(NlogN) atau O(N).
Kesederhanaan Implementasi: Algoritma ini dianggap sederhana karena prinsip kerjanya yang lugas: cukup pilih yang terbaik setiap kali menemukan pilihan dan tidak perlu menengok kembali keputusan yang sudah diambil. Strategi ini sangat efektif untuk menyederhanakan langkah-langkah penyelesaian masalah yang kompleks.
Hemat Memori: Dibandingkan dengan Dynamic Programming (DP), Greedy jauh lebih hemat memori. Hal ini terjadi karena Greedy tidak perlu menyimpan tabel hasil perhitungan sub-masalah (memoization/tabulation) yang biasanya membutuhkan ruang penyimpanan besar.Optimalitas pada Masalah Tertentu: Meskipun tidak selalu menjamin solusi global, Greedy selalu menghasilkan solusi optimal pada masalah yang memiliki sifat Greedy Choice Property dan Optimal Substructure.
Contoh nyatanya ketidakmampuan Greedy mencapai optimal global adalah pada masalah Fractional Knapsack (barang yang boleh dipotong), pemberian uang kembalian dengan sistem pecahan tertentu, serta pengkodean Huffman.
Sangat Efektif untuk Masalah Real-Time: Karena sifatnya yang mengambil keputusan instan ("saat ini"), algoritma Greedy menjadi dasar yang kuat untuk algoritma navigasi seperti Dijkstra dalam mencari jalur terpendek dan penjadwalan aktivitas yang membutuhkan respon cepat.
Secara keseluruhan, dalam spektrum strategi optimasi, Greedy diposisikan sebagai solusi yang paling efisien secara sumber daya (waktu dan memori) selama masalah yang dihadapi memang cocok diselesaikan dengan pendekatan langkah demi langkah yang "serakah".
Dalam konteks strategi optimasi berpikir komputasional, 0/1 Knapsack merupakan masalah klasik di mana Dynamic Programming (DP) menjadi solusi utama karena keterbatasan algoritma Greedy,. Berikut adalah pembahasan mengenai 0/1 Knapsack dalam konteks DP berdasarkan sumber yang tersedia:
1. Definisi Masalah 0/1 Knapsack
Pada masalah 0/1 Knapsack, setiap barang hanya tersedia satu buah dan tidak boleh dipotong atau diambil sebagian,.
Pilihannya hanya dua: mengambil barang tersebut secara utuh (1) atau meninggalkannya (0),. Hal ini berbeda dengan Fractional Knapsack di mana barang boleh dipotong dan bisa diselesaikan secara optimal dengan Greedy,.
2. Mengapa 0/1 Knapsack Membutuhkan DP?
Algoritma Greedy sering kali gagal memberikan solusi optimal pada masalah 0/1 Knapsack karena terlalu fokus pada keuntungan lokal (seperti memilih rasio nilai per berat tertinggi) tanpa mempertimbangkan kombinasi barang secara keseluruhan,.
Contoh Kegagalan Greedy:
Misalkan kapasitas tas 5 kg dengan barang:
A: 1 kg, Nilai $60 (Rasio 60)
B: 2 kg, Nilai $100 (Rasio 50)
C: 3 kg, Nilai $120 (Rasio 40)
Strategi Greedy akan memilih A lalu B (Total Nilai = $160).
Namun, solusi optimal sebenarnya adalah memilih B dan C (Total Nilai = $220).
Dalam kasus ini, DP diperlukan untuk mengevaluasi kombinasi yang lebih baik.
3. Mekanisme Kerja DP pada 0/1 Knapsack
Dynamic Programming menyelesaikan masalah ini dengan memanfaatkan dua syarat utama:
Optimal Substructure (solusi masalah besar dibentuk dari solusi sub-masalah kecil) dan Overlapping Subproblems (menghindari perhitungan berulang pada sub-masalah yang sama).
Evaluasi Pilihan: DP tidak menebak secara instan, melainkan mengevaluasi pilihan untuk setiap barang (i) dan setiap kemungkinan kapasitas (w) menggunakan logika berikut:
DP[i][w]=max(nilai tanpa barang i,nilai dengan barang i)
Penggunaan Tabel (Tabulasi):
Hasil dari setiap sub-masalah disimpan dalam sebuah tabel. Algoritma kemudian memilih kombinasi maksimal dari nilai-nilai yang tersimpan di tabel tersebut untuk memecahkan masalah besarnya.
4. Keunggulan DP dalam Konteks Optimasi
Meskipun DP umumnya lebih lambat dan membutuhkan memori lebih besar daripada Greedy, DP dijamin akan menemukan solusi optimal global jika dirancang dengan benar,
Dalam konteks 0/1 Knapsack, DP memastikan bahwa tidak ada kombinasi barang yang terlewatkan, sehingga hasil akhirnya selalu yang paling maksimal dibandingkan pendekatan Greedy yang hanya mencari jalur tercepat
Linear Programming (Pemrograman Linear) adalah metode penyelesaian masalah dengan memodelkan masalah secara matematis untuk mencari
solusi paling optimal dari suatu masalah dengan beberapa
variabel keputusan, tujuan, dan batasan (kendala).
Misal Sebuah toko roti membuat RotiA dan RotiB.
| Roti A | Roti B | Persediaan |
|---|
| Tepung | 2 kg | 1 kg | 10 kg |
| Gula | 1 kg | 2 kg | 8 kg |
| Keuntungan | Rp4.000 | Rp5.000 | |
Berapa rotiA dan RotiB diproduksi untuk menghasilkan keuntungan terbesar?
Misal x = RotiA dan y = RotiB
Make persamaan matematisnya
Tepung : 2 x + y <= 10
Gula : x + 2y <= 8
Keuntungan K = 4000x + 5000y
Titik yang memenuhi syarat
(0,0), (5,0), (4,2), (0,4)| Titik | Keuntungan |
|---|
| (0,0) | Rp0 |
| (5,0) | Rp20.000 |
| (4,2) | Rp26.000 |
| (0,4) | Rp20.000 |
Keuntungan maksimal di titik 4,2 atau 4 RotiA dan 2 RotiB dengan keuntungan Rp 26.000
Tabel Hubungan 4 Algoritma
| Metode | Cara Berpikir | Kecepatan | Selalu Optimal? |
|---|
| Brute Force | Coba semua kemungkinan | ❌ Sangat lambat | ✅ Ya |
| Dynamic Programming | Simpan solusi submasalah | ⚡ Cepat | ✅ Ya (untuk masalah yang sesuai) |
| Greedy | Ambil yang terbaik sekarang | ⚡⚡ Sangat cepat | ❌ Tidak selalu |
| Linear Programming | Model matematika dengan fungsi objektif dan kendala | ⚡ Cepat untuk kelas masalah tertentu | ✅ Ya (untuk model LP yang valid) |
Link PDF 1.
Berfikir Komputasional Algoritma Greedy, DP dan LP Link Youtube:
Dinamik Programming 
