Kasus Knapsack dengan Algoritma Greedy
Cerita
Bayangkan suatu hari kamu hendak melakukan perjalanan mendaki gunung bersama teman-temanmu. Kamu hanya membawa satu tas dengan kapasitas maksimal 10 kg.
Di depanmu ada lima barang yang bisa dibawa. Setiap barang punya berat dan nilai manfaat yang berbeda. Nilai ini bisa diartikan sebagai seberapa besar manfaat barang tersebut untuk perjalananmu, misalnya ada makanan, obat-obatan, pakaian hangat, atau peralatan memasak.
Daftar barang yang tersedia:
- Barang 1: Berat 6 kg, Nilai 30
- Barang 2: Berat 3 kg, Nilai 14
- Barang 3: Berat 4 kg, Nilai 16
- Barang 4: Berat 2 kg, Nilai 9
- Barang 5: Berat 5 kg, Nilai 20
Karena tas hanya bisa menampung 10 kg, kamu tidak bisa membawa semuanya. Maka muncul pertanyaan: “Barang mana saja yang sebaiknya dibawa agar nilai manfaatnya paling besar, tapi beratnya tidak melebihi kapasitas tas?”
Untuk menjawab pertanyaan ini, kita gunakan algoritma Greedy. Disebut Greedy (rakus) karena cara kerjanya selalu memilih barang yang paling menguntungkan saat itu juga, tanpa menunda atau memikirkan kombinasi lain.
Caranya adalah dengan menghitung rasio nilai per berat (value per weight) dari tiap barang. Barang dengan nilai per kg paling tinggi akan dipilih lebih dulu, karena dianggap paling menguntungkan dibanding berat yang dikorbankan.
Perhitungan Nilai per Kg
- Barang 1 → 30 ÷ 6 = 5.0
- Barang 2 → 14 ÷ 3 ≈ 4.67
- Barang 4 → 9 ÷ 2 = 4.5
- Barang 3 → 16 ÷ 4 = 4.0
- Barang 5 → 20 ÷ 5 = 4.0
Urutan pemilihan barang berdasarkan nilai per kg:
Barang 1 → Barang 2 → Barang 4 → Barang 3 → Barang 5
Selanjutnya kita coba masukkan barang satu per satu ke dalam tas selama masih ada ruang.
Penjelasan Coding GreedyKnapsack
Program GreedyKnapsack diawali dengan mendeklarasikan data barang dalam bentuk
array dua dimensi yang berisi berat, nilai, dan nama barang.
Data ini kemudian diubah menjadi List agar mudah diurutkan.
Proses pengurutan dilakukan berdasarkan rasio nilai ÷ berat
(value per weight) secara descending, sehingga barang dengan rasio terbesar
diprioritaskan terlebih dahulu. Setelah barang terurut, program melakukan perulangan untuk
memeriksa setiap barang: jika kapasitas tas masih cukup, barang tersebut dimasukkan ke tas,
kapasitas berkurang sesuai beratnya, dan total nilai ditambah dengan nilai barang tersebut.
Terakhir, program menampilkan hasil berupa daftar barang yang dipilih serta total nilai yang diperoleh,
yaitu Barang 1 dan Barang 2 dengan total nilai 44.
Kesimpulan
Dengan algoritma Greedy, barang yang akhirnya dipilih untuk dimasukkan ke dalam tas adalah:
- Barang 1 (6 kg, nilai 30)
- Barang 2 (3 kg, nilai 14)
Total berat yang terbawa = 9 kg (tidak melebihi kapasitas 10 kg).
Total nilai yang didapat = 44.
Artinya, kamu bisa membawa dua barang tersebut dan tetap memperoleh manfaat paling besar menurut pendekatan greedy.
Catatan: Metode ini sederhana, cepat, dan praktis, walaupun tidak selalu menjamin hasil benar-benar optimal dalam semua kasus. Namun pada kasus kali ini, strategi greedy memberikan hasil yang cukup baik.
Tidak ada komentar:
Posting Komentar