Masalah Ransel Pecahan: Algoritma Greedy dengan Contoh

Apa itu Strategi Serakah?

Algoritma serakah Memilih pilihan lokal terbaik di setiap langkah dengan harapan bahwa serangkaian optimasi lokal akan menghasilkan solusi optimal secara global. Seperti Pemrograman Dinamis, mereka menargetkan masalah optimasi, tetapi mereka tidak pernah menengok ke belakang untuk mempertimbangkan kembali keputusan sebelumnya.

Algoritma greedy biasanya mudah ditulis, cepat (seringkali dalam waktu linear atau kuadratik), mudah di-debug, dan hemat memori. Kelemahannya adalah hasilnya tidak selalu optimal, sehingga strategi ini hanya berfungsi untuk masalah yang memiliki struktur yang terbukti aman terhadap algoritma greedy.

Strategi greedy menyelesaikan optimasi kombinatorial dengan membangun solusi A satu komponen Ai pada satu waktu. Pada setiap langkah, Anda memilih Ai secara optimal di bawah batasan saat ini dan memperkecil masalah menjadi submasalah yang lebih kecil.

Agar metode greedy dianggap benar, dua sifat berikut harus dipenuhi:

1. Sifat pilihan serakah: Optimum lokal pada setiap langkah mengarah ke optimum global. Pilihan bergantung pada keputusan masa lalu tetapi tidak pada keputusan masa depan.
2. Struktur pendukung optimal: Solusi optimal dari keseluruhan masalah mengandung solusi optimal dari submasalah-submasalahnya.

Algoritma serakah memiliki lima komponen:

1. Sekumpulan kandidat yang digunakan untuk membangun solusi.
2. Fungsi seleksi yang memilih kandidat terbaik berikutnya.
3. Fungsi kelayakan yang memeriksa apakah suatu kandidat dapat memperluas solusi parsial yang ada.
4. Fungsi objektif yang menilai solusi lengkap atau sebagian.
5. Fungsi evaluasi yang memberi sinyal ketika solusi telah selesai.

Ide tentang Orang yang Serakah

Si Serakah mengurutkan paket hanya berdasarkan nilainya:

• Urutkan paket dalam urutan nilai yang menurun.
• Telusuri daftar yang sudah diurutkan dan tambahkan setiap paket ke dalam ransel jika kapasitas yang tersisa masih mencukupi.

Aturan ini tidak selalu memberikan jawaban yang optimal. Contoh kontra:

• Parameter: n = 3, M = 19.
• Paket: {i = 1; W = 14; V = 20}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 8} — nilai tinggi tetapi juga berat tinggi.
• Si Serakah memilih paket 1 dengan nilai total 20, sedangkan pilihan optimal (paket 2, paket 3) mencapai 24.

Ide tentang Serakah Dua

Greedy Two mengurutkan paket hanya berdasarkan beratnya:

• Urutkan paket berdasarkan beratnya dari yang terkecil ke yang terbesar.
• Telusuri daftar yang sudah diurutkan dan tambahkan setiap paket ke dalam ransel jika kapasitas yang tersisa masih mencukupi.

Aturan ini juga gagal menjadi optimal. Contoh kontra:

• Parameter: n = 3, M = 11.
• Paket: {i = 1; W = 5; V = 10}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 28} — ringan tetapi bernilai rendah.
• Greedy Two memilih (paket 1, paket 2) dengan nilai total 26, sedangkan pilihan optimal (paket 3) mencapai 28.

Ide Tiga Serakah

Metode Greedy Three memperbaiki kedua kekurangan tersebut dengan menggabungkan nilai dan bobot menjadi satu kunci peringkat tunggal. Ini adalah metode standar untuk Masalah Knapsack Fraksional.

• Hitung biaya satuan V[i] / W[i] untuk setiap kemasan.
• Urutkan paket berdasarkan harga satuan yang menurun.
• Telusuri daftar yang sudah diurutkan dan tambahkan setiap paket jika kapasitas yang tersisa memungkinkan.

Greedy Three mengurutkan berdasarkan biaya satuan V[i] / W[i]

Ide: Hitung rasio nilai terhadap berat V[i] / W[i] untuk setiap paket, urutkan dalam urutan menurun, dan ambil rasio terbesar yang tersedia terlebih dahulu sampai ransel penuh.

Untuk yang benar Fractional Sebagai variasi, ketika paket berikutnya tidak dapat masuk secara utuh, ambil sebagian yang tepat mengisi kapasitas yang tersisa. Aturan tambahan itulah yang membuat Greedy Three terbukti optimal pada Fractional Knapsack.

Langkah-langkah Algoritma

Untuk varian branch-and-bound 0/1, daftar biaya unit yang diurutkan menggerakkan pohon pencarian:

• Langkah 1: Node akar mewakili ransel kosong. TotalValue = 0. UpperBound = M × biaya satuan maksimum.
• Langkah 2: Buat cabang pada akar berdasarkan jumlah salinan paket dengan rasio terbesar yang dapat ditampung. Untuk setiap cabang, hitung ulang TotalValue, kapasitas tersisa M, dan UpperBound.
• Langkah 3: Kembangkan kemampuan anak dengan UpperBound terbesar terlebih dahulu, dengan harapan dapat menemukan solusi yang tepat dengan cepat.
• Langkah 4: Hapus node mana pun yang UpperBound-nya tidak lebih baik daripada solusi lengkap terbaik saat ini.
• Langkah 5: Ketika setiap node diperluas atau dipangkas, solusi lengkap terbaik saat ini adalah yang optimal.

Kode semu untuk algoritma greedy Fractional Knapsack murni:

Fractional Knapsack (Array W, Array V, int M)
1. for i <- 1 to size(V)
2.     cost[i] <- V[i] / W[i]
3. Sort-Descending(cost)
4. total <- 0
5. i <- 1
6. while (i <= size(V) and M > 0)
7.     if W[i] <= M
8.         M <- M - W[i]
9.         total <- total + V[i]
10.        i <- i + 1
11.    else
12.        total <- total + V[i] * (M / W[i])
13.        M <- 0

Kompleksitas algoritma:

• Menggunakan pengurutan sederhana (seleksi atau gelembung): O(n)²).
• Menggunakan quick sort atau merge sort: O(n log n), didominasi oleh langkah pengurutan.

Java Code untuk Greedy Three

Tentukan KnapsackPackage Kelas dengan bobot, nilai, dan biaya turunan (rasio V/W yang digunakan untuk pengurutan):

public class KnapsackPackage {

    private double weight;
    private double value;
    private Double cost;

    public KnapsackPackage(double weight, double value) {
        super();
        this.weight = weight;
        this.value = value;
        this.cost = Double.valueOf(value / weight);
    }

    public double getWeight() { return weight; }

    public double getValue() { return value; }

    public Double getCost()  { return cost; }
}

Kemudian buatlah fungsi yang mengimplementasikan Greedy Three:

public void knapsackGreProc(int W[], int V[], int M, int n) {
    KnapsackPackage[] packs = new KnapsackPackage[n];
    for (int i = 0; i < n; i++) {
        packs[i] = new KnapsackPackage(W[i], V[i]);
    }

    Arrays.sort(packs, new Comparator<KnapsackPackage>() {
        @Override
        public int compare(KnapsackPackage a, KnapsackPackage b) {
            return b.getCost().compareTo(a.getCost());
        }
    });

    double remain = M;
    double result = 0d;

    for (int i = 0; i < n && remain > 0; i++) {
        if (packs[i].getWeight() <= remain) {
            remain -= packs[i].getWeight();
            result += packs[i].getValue();
            System.out.println("Pack " + i + " - Weight " + packs[i].getWeight()
                             + " - Value " + packs[i].getValue());
        } else {
            double fraction = remain / packs[i].getWeight();
            result += packs[i].getValue() * fraction;
            System.out.println("Pack " + i + " - Fraction " + fraction
                             + " - Value " + packs[i].getValue() * fraction);
            remain = 0;
        }
    }

    System.out.println("Max Value:\t" + result);
}

Fungsi knapsackGreProc() di Java

Penjelasan kode:

1. Bungkus setiap input ke dalam sebuah KnapsackPackage Jadi, kunci pengurutan (rasio V/W) dihitung sebelumnya.
2. Urutkan berdasarkan harga dari yang termurah ke termurah.
3. Ambil setiap kemasan secara utuh jika muat.
4. Ambil sebagian kecil dari kemasan berikutnya untuk mengisi kapasitas yang tersisa.
5. Berhenti segera setelah kapasitas yang tersisa mencapai nol.

Catatan perbaikan: asli Java loop lanjutan i Hanya ketika sebuah paket tidak muat, yang menyebabkan paket yang sama diambil berulang kali. Versi di atas memajukan satu paket per iterasi dan menambahkan langkah pengisian sebagian, sesuai dengan aturan Fractional Knapsack yang sebenarnya.

Java driver yang menjalankan algoritma pada contoh yang sudah dikerjakan:

public void run() {
    int W[] = new int[]{15, 10, 2, 4};
    int V[] = new int[]{30, 25, 2, 6};
    int M = 37;
    int n = V.length;
    knapsackGreProc(W, V, M, n);
}

Python3 Code untuk Greedy Three

Pertama-tama, definisikan KnapsackPackage kelas. Itu __lt__ Metode ini memungkinkan pengurutan langsung berdasarkan biaya:

class KnapsackPackage(object):
    """Knapsack Package Data Class"""

    def __init__(self, weight, value):
        self.weight = weight
        self.value  = value
        self.cost   = value / weight

    def __lt__(self, other):
        return self.cost < other.cost

Kemudian implementasikan rutin Fractional Knapsack:

class FractionalKnapsack(object):

    def knapsackGreProc(self, W, V, M, n):
        packs = [KnapsackPackage(W[i], V[i]) for i in range(n)]
        packs.sort(reverse=True)

        remain = M
        result = 0

        for i in range(n):
            if remain == 0:
                break
            if packs[i].weight <= remain:
                remain -= packs[i].weight
                result += packs[i].value
                print("Pack", i, "- Weight", packs[i].weight, "- Value", packs[i].value)
            else:
                fraction = remain / packs[i].weight
                result += packs[i].value * fraction
                print("Pack", i, "- Fraction", fraction,
                      "- Value", packs[i].value * fraction)
                remain = 0

        print("Max Value:", result)

Fungsi knapsackGreProc() di Python

Catatan perbaikan: asli Python kelas mendefinisikan kosong __init__ tanpa tubuh, yang menimbulkan IndentationErrorVersi di atas menghilangkan konstruktor kosong karena tidak diperlukan.

Driver yang menjalankan algoritma pada contoh pertama:

if __name__ == "__main__":
    W = [15, 10, 2, 4]
    V = [30, 25, 2, 6]
    M = 37
    n = 4

    proc = FractionalKnapsack()
    proc.knapsackGreProc(W, V, M, n)

C# Code untuk Greedy Three

Tentukan KnapsackPackage kelas:

using System;

namespace KnapsackProblem
{
    public class KnapsackPackage
    {
        private double weight;
        private double value;
        private double cost;

        public KnapsackPackage(double weight, double value)
        {
            this.weight = weight;
            this.value  = value;
            this.cost   = value / weight;
        }

        public double Weight { get { return weight; } }
        public double Value  { get { return value; } }
        public double Cost   { get { return cost; } }
    }
}

Implementasikan algoritma Greedy Three dengan langkah pengisian pecahan:

public void KnapsackGreProc(int[] W, int[] V, int M, int n)
{
    KnapsackPackage[] packs = new KnapsackPackage[n];
    for (int k = 0; k < n; k++)
        packs[k] = new KnapsackPackage(W[k], V[k]);

    Array.Sort<KnapsackPackage>(packs,
        (a, b) => b.Cost.CompareTo(a.Cost));

    double remain = M;
    double result = 0d;

    for (int i = 0; i < n && remain > 0; i++)
    {
        if (packs[i].Weight <= remain)
        {
            remain -= packs[i].Weight;
            result += packs[i].Value;
            Console.WriteLine("Pack " + i + " - Weight " + packs[i].Weight
                            + " - Value " + packs[i].Value);
        }
        else
        {
            double fraction = remain / packs[i].Weight;
            result += packs[i].Value * fraction;
            Console.WriteLine("Pack " + i + " - Fraction " + fraction
                            + " - Value " + packs[i].Value * fraction);
            remain = 0;
        }
    }

    Console.WriteLine("Max Value:\t" + result);
}

Fungsi KnapsackGreProc() di C#

Contoh Kontra: Greedy Three pada Knapsack 0/1

Greedy Three optimal untuk varian Fractional, tetapi pada Knapsack 0/1 (di mana item tidak dapat dibagi) dapat dikalahkan. Contoh kontra:

• Parameter: n = 3, M = 10.
• Paket: {i = 1; W = 7; V = 9; biaya = 9/7}, {i = 2; W = 6; V = 6; biaya = 1}, {i = 3; W = 4; V = 4; biaya = 1}.
• Algoritma Greedy Three memilih paket 1 dengan nilai total 9, sedangkan pilihan optimal 0/1 (paket 2, paket 3) mencapai 10.

Pelajaran: gunakan Greedy Three hanya jika pecahan diperbolehkan. Untuk varian 0/1, gunakan Pemrograman Dinamis sebagai gantinya.

Aplikasi dari Desain Ransel Fraksional

• Pemuatan kargo di mana barang cair, bubuk, atau curah dapat dipisahkan berdasarkan berat.
• Alokasi portofolio di berbagai opsi investasi yang menerima pendanaan sebagian.
• Berbagi bandwidth cloud di mana aliran data dapat mengonsumsi sebagian kecil dari kapasitas tautan.
• Penjadwalan CPU di bawah model pembagian waktu bersama dengan beban kerja yang dapat dibagi.
• Alokasi sumber daya AI di mana pekerjaan pelatihan dapat menggunakan sebagian kecil dari GPU.

Pertanyaan Umum Demo Slot