🎒 Kasus Knapsack: Solusi dengan Brute Force
Analisis untuk memaksimalkan nilai barang dalam tas berkapasitas terbatas dengan mencoba semua kemungkinan solusi yang ada.
📌 Definisi dan Karakteristik Brute Force
Brute Force adalah sebuah pendekatan algoritma yang memecahkan masalah dengan cara paling mendasar: **mencoba semua kemungkinan solusi** secara sistematis, lalu memilih solusi yang terbaik. Ini seperti mencoba semua kunci di gantungan satu per satu untuk membuka pintu.
- Mudah dipahami: Logikanya sangat lugas dan mudah diimplementasikan.
- Pasti menemukan solusi: Karena semua kemungkinan dicoba, algoritma ini dijamin akan menemukan jawaban yang paling optimal.
- Tidak efisien untuk data besar: Jumlah kombinasi bisa menjadi sangat besar, sehingga membutuhkan waktu komputasi yang lama.
📌 Data Kasus
Kita dihadapkan pada sebuah tas dengan kapasitas maksimal 10 kg dan 5 barang yang bisa dipilih:
| Barang | Berat (kg) | Nilai |
|---|---|---|
| 1 | 6 | 30 |
| 2 | 3 | 14 |
| 3 | 4 | 16 |
| 4 | 2 | 9 |
| 5 | 5 | 20 |
📌 Perhitungan Semua Kombinasi yang Valid
Dengan metode Brute Force, kita harus mengevaluasi semua kemungkinan kombinasi dan menyaring yang beratnya tidak melebihi 10 kg. Berikut adalah semua kombinasi yang valid beserta hasilnya:
| Kombinasi Barang | Total Berat (kg) | Total Nilai |
|---|---|---|
| {4} | 2 | 9 |
| {2} | 3 | 14 |
| {3} | 4 | 16 |
| {5} | 5 | 20 |
| {1} | 6 | 30 |
| {2, 4} | 5 | 23 |
| {3, 4} | 6 | 25 |
| {2, 3} | 7 | 30 |
| {4, 5} | 7 | 29 |
| {2, 5} | 8 | 34 |
| {1, 4} | 8 | 39 |
| {3, 5} | 9 | 36 |
| {1, 2} | 9 | 44 |
| {2, 3, 4} | 9 | 39 |
| {2, 4, 5} | 10 | 43 |
| {1, 3} | 10 | 46 |
Dari tabel di atas, terlihat jelas bahwa kombinasi {1, 3} memberikan nilai tertinggi, yaitu 46, dengan berat yang pas di kapasitas 10 kg.
📌 Contoh Pseudocode
INPUT: daftar_barang, kapasitas_tas OUTPUT: kombinasi_terbaik, nilai_maksimal LANGKAH: 1. Inisialisasi nilai_maksimal = 0 2. Inisialisasi kombinasi_terbaik = [] 3. UNTUK SETIAP kemungkinan_kombinasi DARI daftar_barang: 4. hitung total_berat dari kemungkinan_kombinasi 5. hitung total_nilai dari kemungkinan_kombinasi 6. 7. JIKA total_berat <= kapasitas_tas DAN total_nilai > nilai_maksimal: 8. nilai_maksimal = total_nilai 9. kombinasi_terbaik = kemungkinan_kombinasi 10. 11. KEMBALIKAN kombinasi_terbaik dan nilai_maksimal
👉 Kesimpulan
Setelah mengevaluasi semua kemungkinan yang ada, solusi optimal untuk masalah Knapsack ini adalah dengan memilih Barang 1 dan Barang 3.
- Total Berat: 6 kg + 4 kg = 10 kg
- Total Nilai Maksimal: 30 + 16 = 46
Metode Brute Force, meskipun tidak efisien untuk data dalam jumlah besar, terbukti sangat efektif dan dapat diandalkan untuk menemukan solusi yang paling optimal pada kasus dengan skala kecil.
Posting Komentar