algoritma greedy
TRANSCRIPT
Algoritma Greedy
ALGORITMA GREEDYAnnisa Rahmawati Dipa Dwinanda Djamal Tika Riskawati Syifa Afifah Fitriani Yana Dwiputra Nugraha 1002341 1005250 1001124 1000110 1005247
Algoritma Greedy
PENGERTIAN ALGORITMA GREEDYAlgoritma greedy merupakan metode yang paling populer memecahkan persoalan optimasi. Sesuai dengan namanya, greedy berarti rakus atau tamak. Prinsip dari algoritma ini adalah take what you can get now!
Algoritma Greedy
Pendekatan yang digunakan di dalam algoritma greedy adalah membuat pilihan yang tampaknya memberikan perolehan terbaik, yaitu dengan membuat pilihan optimum lokal (local optimum) pada setiap langkah dengan harapan bahwa sisanya mengarah ke solusi optimum global (global optimum).
Algoritma Greedy
Pseudo-code algoritma greedy adalah sebagai berikut:procedure greedy(input C: himpunan_kandidat; output S : himpunan_solusi) { menentukan solusi optimum dari persoalan optimasi dengan algoritma greedy Masukan: himpunan kandidat C Keluaran: himpunan solusi S } Deklarasi x : kandidat;
Algoritma: S{} { inisialisasi S dengan kosong }
while (belum SOLUSI(S)) and (C {} ) doxSELEKSI(C); C C - {x} if LAYAK(S {x}) then SS {x} endif endwhile {SOLUSI(S) sudah diperoleh or C = {} } { pilih sebuah kandidat dari C} { elemen himpunan kandidat berkurang satu }
Algoritma Greedy
CONTOH ALGORITMA GREEDY
1. Penukaran Uang Strategi greedy yang digunakan adalah: Pada setiap langkah, pilihlah koin dengan nilai sebesar mungkin dari himpunan koin yang tersisa dengan syarat (kendala) tidak melebihi nilai uang yang ditukarkan.
Algoritma Greedy
elemen-elemen algoritma greedy-nya adalah: 1. Himpunan kandidat: 1, 5, 10, 25. 2. Himpunan solusi: 25, 5, 1, 1. 3. Fungsi seleksi: 25. 4. Fungsi layak: memeriksa apakah nilai total dari himpunan koin yang dipilih tidak melebihi jumlah uang yang harus dibayar. 5. Fungsi obyektif: jumlah koin yang digunakan minimum.
Algoritma Greedy
2. Knapsack Problem Strategi greedy untuk memilih objek yang akan dimasukkan ke Knapsack(ransel) yaitu : Greedy by profit. Greedy by weight. Greedy by density.
Algoritma Greedy
Contoh Tinjau persoalan 0/1 Knapsack dengan n = 4. w1 = 2; p1 = 12 w2 = 5; p1 = 15 w3 = 10; p1 = 50 w4 = 5; p1 = 10 Kapasitas knapsack W = 16
Algoritma Greedy
Jawab :Properti objeki 1 2 3 wi 6 5 10 pi 12 15 50 pi /wi 2 3 5 profit 0 1 1
Greedy byweight 1 1 0 density 0 1 1
SolusiOptimal 0 1 1
4
5
10
2
0Total bobot 15
116 37
015 65
015 65
Total keuntungan 65
Algoritma Greedy
KESIMPULAN Algoritma greedy adalah algoritma untuk mencari solusi terbaik dengan prinsip take what you can get now! tanpa melihat kedepannya.