Algoritma greedy

Merupakan metode pemecahan masalah yang mengandalkan strategi "memilih yang terbaik pada saat ini" dengan harapan bahwa pilihan lokal terbaik akan mengarah ke solusi global yang optimal. Prinsip dasarnya adalah membuat keputusan yang paling baik (optimum) pada setiap langkah dari algoritma, tanpa memperhatikan konsekuensi keputusan tersebut di masa depan.

Prinsip Dasar

1. Pilih Langkah Terbaik Saat Ini: Pilih opsi yang tampak terbaik pada saat ini tanpa mempertimbangkan dampaknya pada keputusan di masa depan.
2. Kemajuan Berkelanjutan: Terus pilih langkah terbaik secara lokal sampai solusi lengkap tercapai.
3. Kriteria Akhir: Verifikasi apakah solusi yang diperoleh memenuhi kriteria optimalitas untuk masalah tersebut.

Kapan Menggunakan Algoritma Greedy?

Algoritma greedy tidak selalu memberikan solusi optimal untuk semua jenis masalah. Namun, ia sangat efektif untuk masalah yang memiliki dua sifat penting:

1. Substruktur Optimal: Solusi optimal dari masalah dapat dibangun dari solusi optimal sub-masalahnya.
2. Propertis Greedy: Solusi global dapat dibangun dengan memilih langkah-langkah yang tampaknya terbaik secara lokal.

Contoh Masalah yang Umum dipecahkan dengan Algoritma Greedy

1. Masalah Koin (Coin Change Problem)

Masalah: Diberikan denominasi koin dan jumlah uang yang ingin ditukar, temukan jumlah minimum koin yang dibutuhkan.

Contoh: Denominasi koin: 1, 3, 4 Jumlah yang ingin ditukar: 6

Solusi Greedy:

1. Pilih koin dengan nilai terbesar yang kurang dari atau sama dengan 6. Dalam hal ini, koin 4.
2. Kurangi 6 dengan 4, sisa 2.
3. Pilih koin 1 dua kali untuk sisa 2.
4. Total koin adalah 1 koin 4 dan 2 koin 1, sehingga 3 koin secara keseluruhan.

Implementasi dalam C++:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minCoins(const vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    
    for (int i = 1; i <= amount; ++i) {
        for (int coin : coins) {
            if (i - coin >= 0) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    
    return dp[amount] > amount ? -1 : dp[amount];
}

int main() {
    vector<int> coins = {1, 3, 4};
    int amount = 6;
    std::cout << "Minimum koin yang diperlukan: " << minCoins(coins, amount) << endl;
    return 0;
}

2. Masalah Knapsack 0/1 (Subset Sum)

Masalah: Diberikan kapasitas knapsack dan beberapa item dengan nilai dan berat, pilih item yang akan dimasukkan ke dalam knapsack untuk memaksimalkan nilai total tanpa melebihi kapasitas knapsack.

Solusi Greedy:

1. Hitung rasio nilai terhadap berat untuk setiap item.
2. Urutkan item berdasarkan rasio ini secara menurun.
3. Masukkan item dengan rasio tertinggi ke dalam knapsack sebanyak mungkin sampai kapasitas penuh.

Implementasi dalam C++:

#include <iostream>
#include <vector>
#include <algorithm>

using namacpace std;

struct Item {
    int value;
    int weight;
    double ratio;
};

bool compare(Item a, Item b) {
    return a.ratio > b.ratio;
}

double knapsackGreedy(std::vector<Item>& items, int capacity) {
    sort(items.begin(), items.end(), compare);
    double totalValue = 0.0;
    int currentWeight = 0;

    for (const auto& item : items) {
        if (currentWeight + item.weight <= capacity) {
            currentWeight += item.weight;
            totalValue += item.value;
        } else {
            int remainingWeight = capacity - currentWeight;
            totalValue += item.value * (static_cast<double>(remainingWeight) / item.weight);
            break;
        }
    }

    return totalValue;
}

int main() {
    vector<Item> items = {{60, 10, 6.0}, {100, 20, 5.0}, {120, 30, 4.0}};
    int capacity = 50;
    cout << "Nilai maksimum yang dapat dicapai: " << knapsackGreedy(items, capacity) << endl;
    return 0;
}

Kelebihan dan Kekurangan

Kelebihan:

• Sederhana dan cepat untuk diterapkan.
• Dapat memberikan solusi yang baik dalam waktu yang singkat untuk beberapa masalah.

Kekurangan:

• Tidak selalu memberikan solusi optimal untuk semua masalah.
• Hasil bisa sangat bergantung pada urutan langkah yang diambil.

Beberapa contoh algoritma greedy yang sering diterapkan dalam konteks lingkungan sekolah atau pembelajaran. 

1. Masalah Penjadwalan Kelas

Masalah: Diberikan sejumlah kelas dengan waktu mulai dan waktu selesai, buatlah jadwal kelas yang memaksimalkan jumlah kelas yang dapat diambil tanpa adanya tabrakan waktu.

Contoh Solusi: Menggunakan algoritma greedy untuk memilih kelas yang selesai lebih awal dan tidak tumpang tindih dengan kelas yang sudah dijadwalkan.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Class {
    int start;
    int end;
};

bool compare(Class a, Class b) {
    return a.end < b.end; // Urutkan berdasarkan waktu selesai
}

void scheduleClasses(std::vector<Class>& classes) {
    sort(classes.begin(), classes.end(), compare); // Urutkan kelas berdasarkan waktu selesai
    cout << "Jadwal Kelas yang dipilih:" << endl;

    int n = classes.size();
    int i = 0; // Pilih kelas pertama
    cout << "Kelas (" << classes[i].start << ", " << classes[i].end << ")" << endl;

    for (int j = 1; j < n; ++j) {
        if (classes[j].start >= classes[i].end) {
            cout << "Kelas (" << classes[j].start << ", " << classes[j].end << ")" << endl;
            i = j;
        }
    }
}

int main() {
    vector<Class> classes = {{9, 10}, {11, 12}, {10, 11}, {13, 14}, {12, 13}};
    scheduleClasses(classes);
    return 0;
}

2. Masalah Pemilihan Buku (Book Selection Problem)

Masalah: Diberikan sejumlah buku dengan waktu mulai dan waktu selesai untuk setiap buku dan waktu total yang tersedia. Pilih buku-buku yang memaksimalkan jumlah buku yang dibaca tanpa melebihi waktu yang tersedia.

Contoh Solusi: Menggunakan algoritma greedy untuk memilih buku yang memerlukan waktu paling sedikit sehingga kita dapat membaca lebih banyak buku.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Book {
    int time;
};

bool compare(Book a, Book b) {
    return a.time < b.time; // Urutkan berdasarkan waktu yang dibutuhkan untuk membaca
}

int selectBooks(std::vector<Book>& books, int availableTime) {
    ort(books.begin(), books.end(), compare); // Urutkan buku berdasarkan waktu yang dibutuhkan
    int totalBooks = 0;
    int totalTime = 0;

    for (const auto& book : books) {
        if (totalTime + book.time <= availableTime) {
            totalTime += book.time;
            totalBooks++;
        } else {
            break;
        }
    }

    return totalBooks;
}

int main() {
    vector<Book> books = {{3}, {2}, {1}, {4}, {2}};
    int availableTime = 6; // Waktu total yang tersedia
    std::cout << "Jumlah buku yang dapat dibaca: " << selectBooks(books, availableTime) << std::endl;
    return 0;
}

3. Masalah Penjadwalan Ujian

Masalah: Diberikan sejumlah ujian dengan waktu mulai dan waktu selesai, pilih ujian-ujian yang dapat diambil tanpa saling bertabrakan.

Contoh Solusi: Menggunakan algoritma greedy yang memilih ujian yang selesai lebih awal untuk memaksimalkan jumlah ujian yang dapat diambil.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Exam {
    int start;
    int end;
};

bool compare(Exam a, Exam b) {
    return a.end < b.end; // Urutkan berdasarkan waktu selesai
}

void scheduleExams(std::vector<Exam>& exams) {
    sort(exams.begin(), exams.end(), compare); // Urutkan ujian berdasarkan waktu selesai
    cout << "Jadwal Ujian yang dipilih:" << endl;

    int n = exams.size();
    int i = 0; // Pilih ujian pertama
    cout << "Ujian (" << exams[i].start << ", " << exams[i].end << ")" << endl;

    for (int j = 1; j < n; ++j) {
        if (exams[j].start >= exams[i].end) {
            cout << "Ujian (" << exams[j].start << ", " << exams[j].end << ")" << endl;
            i = j;
        }
    }
}

int main() {
    vector<Exam> exams = {{1, 2}, {3, 4}, {0, 6}, {5, 7}, {8, 9}};
    scheduleExams(exams);
    return 0;
}

4. Masalah Pembagian Waktu Belajar

Masalah: Diberikan sejumlah kegiatan dengan waktu mulai dan selesai, bagi waktu belajar Anda sehingga memaksimalkan jumlah kegiatan yang dapat diselesaikan.

Contoh Solusi: Menggunakan algoritma greedy untuk memilih kegiatan yang memerlukan waktu paling sedikit untuk memaksimalkan jumlah kegiatan.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Activity {
    int start;
    int end;
};

bool compare(Activity a, Activity b) {
    return a.end < b.end; // Urutkan berdasarkan waktu selesai
}

int maximizeActivities(std::vector<Activity>& activities) {
    sort(activities.begin(), activities.end(), compare); // Urutkan kegiatan berdasarkan waktu selesai
    int count = 0;
    int lastEndTime = -1;

    for (const auto& activity : activities) {
        if (activity.start >= lastEndTime) {
            lastEndTime = activity.end;
            count++;
        }
    }

    return count;
}

int main() {
    vector<Activity> activities = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {8, 9}};
    cout << "Jumlah kegiatan yang bisa diselesaikan: " << maximizeActivities(activities) << std::endl;
    return 0;
}