⚡ Solusi Knapsack dengan Algoritma Greedy

Pendekatan cepat untuk menyelesaikan masalah Knapsack dengan memilih barang yang paling "berharga" per satuan beratnya terlebih dahulu.

📌 Konsep Dasar Algoritma Greedy

Pendekatan yang paling umum dalam algoritma Greedy untuk masalah knapsack adalah dengan memilih barang berdasarkan rasio nilai/berat (value/weight) yang paling tinggi. Tujuannya adalah untuk memasukkan barang yang memberikan "nilai paling besar per kilogramnya" terlebih dahulu.

Langkah 1: Hitung Rasio Nilai/Berat

Pertama, kita hitung rasio nilai dibagi berat untuk setiap barang guna menentukan prioritasnya.

Barang	Perhitungan (Nilai / Berat)	Rasio
Barang 1	30 / 6 kg	5.00
Barang 2	14 / 3 kg	4.67
Barang 3	16 / 4 kg	4.00
Barang 4	9 / 2 kg	4.50
Barang 5	20 / 5 kg	4.00

Langkah 2: Urutkan Barang Berdasarkan Rasio

Sekarang, kita urutkan barang dari rasio tertinggi hingga terendah untuk dijadikan acuan pengambilan.

1. Barang 1 (Rasio: 5.00)
2. Barang 2 (Rasio: 4.67)
3. Barang 4 (Rasio: 4.50)
4. Barang 3 (Rasio: 4.00)
5. Barang 5 (Rasio: 4.00)

Langkah 3: Proses Pengisian Tas (Kapasitas 10 kg)

Kita mulai memasukkan barang ke dalam tas sesuai urutan prioritas, selama kapasitas tas masih mencukupi.

1. Ambil Barang 1 (6 kg, nilai 30)?
✅ Ya, tas masih muat (kapasitas 10 kg).
Barang Dipilih: {1}, Sisa Kapasitas: 10 - 6 = 4 kg, Total Nilai: 30

---

2. Ambil Barang 2 (3 kg, nilai 14)?
✅ Ya, tas masih muat (sisa kapasitas 4 kg).
Barang Dipilih: {1, 2}, Sisa Kapasitas: 4 - 3 = 1 kg, Total Nilai: 30 + 14 = 44

---

3. Ambil Barang 4 (2 kg, nilai 9)?
❌ Tidak, tas tidak muat (sisa kapasitas hanya 1 kg, butuh 2 kg).

---

4. Ambil Barang 3 (4 kg, nilai 16)?
❌ Tidak, tas tidak muat.

Proses selesai karena tidak ada lagi barang dalam urutan prioritas yang bisa dimasukkan.

✅ Hasil Akhir (Solusi Greedy)

Berdasarkan algoritma Greedy dengan prioritas rasio nilai/berat, barang yang terpilih adalah:

• Barang 1 (Berat: 6 kg, Nilai: 30)
• Barang 2 (Berat: 3 kg, Nilai: 14)

Total Berat: 6 + 3 = 9 kg
Total Nilai: 30 + 14 = 44

Catatan Penting: Algoritma Greedy sangat cepat dan memberikan solusi yang "cukup baik". Namun, solusi ini (nilai 44) belum tentu yang paling optimal. Sebagai perbandingan, solusi optimal dari masalah ini (yang ditemukan oleh Brute Force) adalah mengambil Barang 1 dan 3 dengan total nilai 46.

💾 Lampiran Kode

Pseudocode Algoritma

FUNGSI GreedyKnapsack(daftar_barang, kapasitas_maksimal)

  // Langkah 1: Hitung rasio nilai/berat untuk setiap barang
  UNTUK SETIAP barang DALAM daftar_barang
    barang.rasio = barang.nilai / barang.berat
  SELESAI UNTUK

  // Langkah 2: Urutkan daftar barang berdasarkan rasio secara menurun
  URUTKAN daftar_barang SECARA MENURUN BERDASARKAN barang.rasio

  // Langkah 3: Isi tas dengan barang sesuai urutan prioritas
  total_berat = 0
  total_nilai = 0
  barang_terpilih = []

  UNTUK SETIAP barang DALAM daftar_barang YANG SUDAH DIURUTKAN
    JIKA (total_berat + barang.berat) <= kapasitas_maksimal MAKA
      TAMBAHKAN barang KE barang_terpilih
      total_berat = total_berat + barang.berat
      total_nilai = total_nilai + barang.nilai
    AKHIR JIKA
  SELESAI UNTUK

  // Kembalikan hasilnya
  KEMBALIKAN barang_terpilih, total_berat, total_nilai

AKHIR FUNGSI
            

Implementasi Kode (Java)

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class KnapsackSederhana {

    /**
     * Menggunakan 'record' untuk membuat kelas data Barang menjadi satu baris.
     * Java otomatis membuat constructor, getters (spt. nama(), berat()), equals(), dll.
     */
    public record Barang(String nama, int berat, int nilai, double rasio) {
        // Custom constructor untuk menghitung rasio secara otomatis
        public Barang(String nama, int berat, int nilai) {
            this(nama, berat, nilai, (double) nilai / berat);
        }
    }

    public static void main(String[] args) {
        // --- Data Barang dari Kasus ---
        var daftarBarang = new ArrayList<>(List.of(
            new Barang("Barang 1", 6, 30),
            new Barang("Barang 2", 3, 14),
            new Barang("Barang 3", 4, 16),
            new Barang("Barang 4", 2, 9),
            new Barang("Barang 5", 5, 20)
        ));

        int kapasitasTas = 10;

        // Langkah 1 & 2: Urutkan list langsung
        daftarBarang.sort(Comparator.comparingDouble(Barang::rasio).reversed());
        
        // Langkah 3: Masukkan barang ke dalam tas
        var barangTerpilih = new ArrayList();
        int totalBerat = 0;
        int totalNilai = 0;

        for (var barang : daftarBarang) {
            if (totalBerat + barang.berat() <= kapasitasTas) {
                barangTerpilih.add(barang);
                totalBerat += barang.berat();
                totalNilai += barang.nilai();
            }
        }

        // --- Menampilkan Hasil ---
        System.out.println("--- Hasil Akhir Algoritma Greedy Knapsack (Java) ---");
        System.out.println("\nBarang yang dipilih untuk dibawa:");
        for (var barang : barangTerpilih) {
            System.out.printf("- %s (Berat: %d kg, Nilai: %d)\n",
                barang.nama(), barang.berat(), barang.nilai());
        }

        System.out.println("\n--- Rekapitulasi ---");
        System.out.printf("Total Berat Barang : %d kg (dari kapasitas %d kg)\n",
            totalBerat, kapasitasTas);
        System.out.printf("Total Nilai Barang : %d\n", totalNilai);
    }
}