TUGAS 2 ALGORITMA (BRUTE FORCE)

 

https://pin.it/6jJcZzm5y

ALGORITMA BRUTE FORCE

Kasus : Memilih barang ke tas (Knapsack)

Kamu punya tas dengan kapasitas 10kg. Ada 5 barang dengan berat dan nilai yang berbeda. Kamu ingin membawa barang dengan total nilainya paling besar, tapi tidak boleh lebih dari total 10kg.

Data barang (berat, nilai):

 • Barang 1: (6 kg, 30)

 • Barang 2: (3 kg, 14) 

 • Barang 3: (4 kg, 16) 

 • Barang 4: (2 kg, 9)

 • Barang 5: (5 kg, 20) 

Tujuan : Pilih barang apa saja yang dibawa agar total nilainya paling besar.

PENYELESAIAN :

1. Pahami Masalah 

• Kapasitas = 10kg
• Barang = Ada 5 buah, masing-masing punya berat dan nilai
• Tujuan = pilih barang yang totalnya 10kg dengan nilai maksimal

2. Konsep Algoritma

    Brute Force = Coba semua kemungkinan kombinasi barang, lalu ambil yang terbaik 

    

    Karena ada 5 barang, jadi setiap barang bisa di pilih(1) atau tidak di pilih(0)

    Total kombinasi = 2 pangkat 5 = 32 Kombinasi

3. Cari Semua Kombinasi 

    Disini saya hitung kombinasi yang memenuhi syarat (≤10 kg):

• {1} → berat = 6kg, nilai = 30 

• {2} → berat = 3kg, nilai = 14 

• {3} → berat = 4kg, nilai = 16 

• {4} → berat = 2kg, nilai = 9 

• {5} → berat = 5kg, nilai = 20 

• {1,2} → berat = 9kg, nilai = 44 

• {1,3} → berat = 10kg, nilai = 46 

• {1,4} → berat = 8kg, nilai = 39 

• {1,5} → berat = 11 

• {2,3} → berat = 7kg, nilai = 30 

• {2,4} → berat = 5kg, nilai = 23 

• {2,5} → berat = 8kg, nilai = 34 

• {3,4} → berat = 6kg, nilai = 25 

• {3,5} → berat = 9kg, nilai = 36 

• {4,5} → berat = 7kg, nilai = 29 

• {2,3,4} → berat = 9kg, nilai = 39 

• {2,3,5} → berat = 12 

• {2,4,5} → berat = 10kg, nilai = 43 

• {3,4,5} → berat = 11kg 

• {1,2,3} → berat = 13kg 

• {1,2,4} → berat = 11kg 

• {1,3,4} → berat = 12kg 

• {1,2,5} → berat = 14kg 

• dst (masih ada kombinasi tapi banyak yang lebih dari 10kg)

4. Kemudian saya cari nilai terbesar dari kemungkinan di atas yang tidak melewati 10kg : 

    

• {1,2} → berat = 9kg, nilai = 44 

• {1,3} → berat = 10kg, nilai = 46 

• {1,4} → berat = 8kg, nilai = 39 

• {2,5} → berat = 8kg, nilai = 34 

• {2,3,4} → berat = 9kg, nilai = 39 

• {2,4,5} → berat = 10kg, nilai = 43 

         Disini dapat lihat, kombinasi terbaik/terbesar nilainya adalah 46 yang mana barang yang di ambil yaitu barang 1 dan barang 3 yang beratnya yaitu 10kg dengan total nilai 46 (terbesar).

    

KODE PROGRAM : 

CODE

CODE

OUTPUT

PSEUDOCODE : 

1. Kita punya daftar barang, setiap barang ada beratnya dan nilainya.

2. Kita juga punya tas dengan kapasitas tertentu (maksimal 10 kg).

3. Tujuannya: cari kombinasi barang yang masuk tas supaya total nilainya paling besar, tapi beratnya tidak melebihi kapasitas.

---

Langkah-langkah:

1. Hitung jumlah barang.

2. Bayangkan semua kemungkinan cara memilih barang.

   • Setiap barang ada 2 pilihan: diambil atau tidak diambil.

   • Kalau ada 5 barang → total ada $2^5=\mathrm{<span\; class="base"><span\; class="strut"></span><span\; class="mord">32 </span>kemungkinan.</span>}$

3. Untuk setiap kemungkinan:

   • Hitung total berat barang-barang yang diambil.

   • Hitung juga total nilai barang-barang itu.

4. Kalau total berat ≤ kapasitas tas:

   • Bandingkan nilai total dengan nilai terbaik yang sudah ada.

   • Kalau lebih besar, simpan kombinasi ini sebagai kombinasi terbaik.

5. Setelah semua kemungkinan dicoba, lihat kombinasi terbaik yang tersimpan.

6. Tampilkan:

   • Barang apa saja yang dipilih.

   • Total berat barang tersebut.

   • Total nilainya.