Tugas 3 ALgoritma

ALGORITMA GREEDY

Pengertian Algoritma Greedy

Algoritma Greedy adalah metode pemecahan masalah yang membuat pilihan terbaik (paling optimal) yang tersedia pada setiap langkahnya dengan harapan akan menemukan solusi terbaik secara keseluruhan (optimal global). Dengan kata lain, algoritma ini "rakus" atau "serakah" karena tidak pernah mempertimbangkan konsekuensi jangka panjang dari pilihan yang dibuatnya. Setelah sebuah pilihan diambil, pilihan itu tidak akan pernah diubah lagi.

Karakteristik Utama

• Selalu Lokal Optimal: Hanya fokus pada pilihan terbaik saat ini.
• Tidak Pernah Mundur: Keputusan yang sudah diambil bersifat final dan tidak pernah ditinjau ulang (tidak ada backtracking).
• Cepat dan Sederhana: Biasanya lebih mudah diimplementasikan dan lebih cepat dieksekusi daripada algoritma lain seperti Dynamic Programming.

---

Contoh Kasus: Penjadwalan Pekerjaan

4) Kasus: Menyusun jadwal kerja (Scheduling)

Cerita: Ada 5 pekerjaan yang harus dikerjakan 1 mesin secara berurutan (tidak bisa paralel). Setiap pekerjaan punya waktu pengerjaan dan bobot penting. Kita ingin mengatur urutan kerja agar “total waktu selesai × bobot” sekecil mungkin.

Data pekerjaan (durasi, bobot):

• A: (3 jam, bobot 4)
• B: (2 jam, bobot 2)
• C: (5 jam, bobot 10)
• D: (1 jam, bobot 1)
• E: (4 jam, bobot 3)

Tujuan: Cari urutan pekerjaan supaya total “waktu selesai × bobot” minimum.

Pseudocode

1. Siapkan data pekerjaan (nama, durasi, bobot).
2. Hitung rasio (durasi / bobot) untuk setiap pekerjaan.
3. Urutkan semua pekerjaan berdasarkan rasio terkecil.
4. Hitung total biaya dengan menjumlahkan biaya setiap pekerjaan sesuai urutan.
5. Tampilkan urutan pekerjaan dan total biaya minimum.

Implementasi Kode Java

public class Soal4 {
    public static void main(String[] args) {
        // Siapkan data dan hitung rasionya
        String[] nama = {"A", "B", "C", "D", "E"};
        int[] durasi = {3, 2, 5, 1, 4};
        int[] bobot = {4, 2, 10, 1, 3};
        double[] rasio = new double[5];

        for (int i = 0; i < 5; i++) {
            rasio[i] = (double) durasi[i] / bobot[i];
        }

        // Urutkan semua data berdasarkan rasio terkecil (Bubble Sort)
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4 - i; j++) {
                if (rasio[j] > rasio[j + 1]) {
                    // Tukar rasio
                    double tempRasio = rasio[j];
                    rasio[j] = rasio[j + 1];
                    rasio[j + 1] = tempRasio;

                    // Tukar nama
                    String tempNama = nama[j];
                    nama[j] = nama[j + 1];
                    nama[j + 1] = tempNama;

                    // Tukar durasi
                    int tempDurasi = durasi[j];
                    durasi[j] = durasi[j + 1];
                    durasi[j + 1] = tempDurasi;

                    // Tukar bobot
                    int tempBobot = bobot[j];
                    bobot[j] = bobot[j + 1];
                    bobot[j + 1] = tempBobot;
                }
            }
        }

        // Hitung total biaya dan tampilkan hasilnya
        long totalBiaya = 0;
        long waktuSelesai = 0;

        System.out.print("Urutan pekerjaan terbaik: ");
        for (int i = 0; i < 5; i++) {
            waktuSelesai += durasi[i];
            totalBiaya += waktuSelesai * bobot[i];
            System.out.print(nama[i] + (i == 4 ? "" : ", "));
        }

        System.out.println("\nTotal Biaya Minimum: " + totalBiaya);
    }
}

OUTPUTNYA

Urutan pekerjaan terbaik: C, A, B, D, E 
Total Biaya Minimum: 158

---

Kesimpulan Cara Kerja Algoritma

Dari kode di atas, dapat disimpulkan bahwa cara kerja algoritma Greedy untuk masalah penjadwalan ini adalah sebagai berikut:

1. Hitung Prioritas Setiap Pekerjaan
   Langkah pertama adalah menghitung "tingkat efisiensi" atau rasio dari setiap pekerjaan dengan rumus `durasi / bobot`.
   Pekerjaan A: 3 / 4 = 0.75
   Pekerjaan B: 2 / 2 = 1.0
   Pekerjaan C: 5 / 10 = 0.5
   Pekerjaan D: 1 / 1 = 1.0
   Pekerjaan E: 4 / 3 = 1.33
2. Pilih Pekerjaan Paling Efisien (Rasio Terkecil)
   Greedy akan memilih pekerjaan dengan rasio terkecil sebagai yang pertama dikerjakan, yaitu **Pekerjaan C (rasio 0.5)**.
3. Pilih Pekerjaan Berikutnya dari yang Tersisa
   Dari sisa pekerjaan, Greedy kembali memilih yang rasionya terkecil, yaitu **Pekerjaan A (rasio 0.75)**.
4. Ulangi Hingga Semua Pekerjaan Terjadwal
   Proses ini diulangi terus. Jika ada rasio yang sama (seperti B dan D), urutannya tidak terlalu berpengaruh pada hasil akhir. Pilihan berikutnya adalah B, lalu D, dan terakhir E.
5. Susun Urutan Final
   Setelah semua pilihan dibuat, didapatkan urutan pekerjaan yang optimal: Urutan Final: C → A → B → D → E
6. Hitung Total Biaya Minimum
   Dengan urutan tersebut, program menghitung total biaya penalti, yang merupakan solusi paling minimum yang bisa didapatkan.