Kasus Pemilihan Buku dengan Algoritma Knapsack

TUGAS 1 ALGORITMA

Nama : Sitti Patima

Kelas : Informatika B

NIM  : D0224013

1. Kasus

Seorang siswa ingin membawa buku di dalam tasnya. Kapasitas tas hanya 5 kg. Ada beberapa buku dengan bobot dan nilai kepentingan berbeda. Dia ingin memilih buku yang paling penting tanpa melebihi kapasitas tas.

a. Input

1. Buku B1: bobot 1kg, nilai 2.

2. Buku B2: bobot 2kg, nilai 4.

3. Buku B3: bobot 3kg, nilai 5.

4. Buku B4: bobot 4kg, nilai 6.

b. Proses (Langkah-langkah Knapsack)

1. Mengecek semua kombinasi buku yang bisa masuk.

2. Menghitung total bobot dan nilai setiap kombinasi.

3. Memilih kombinasi dengan nilai terbesar tapi bobot ≤ 5.

Contoh Kombinasi:

a. (B1,B2) → bobot 3, nilai 6.

b. (B1,B3) → bobot 4, nilai 7.

c. (B1,B4) → bobot 5, nilai 8.

d. (B2,B3) → bobot 5, nilai 9.

e. (B2,B4) → bobot 6, nilai 11.

f. (B3,B4) → bobot 7, nilai 13.

c. Output

Dari beberapa contoh kombinasi di atas, kombinasi terbaik adalah (B2,B3) dengan bobot 5 kg dan nilai 9. Bobotnya sesuai dengan kapasitas tas dan memiliki nilai kepentingan tertinggi.

2. Tentang Algoritma

a. Apakah efektif?

1. Algoritma Knapsack memastikan pilihan terbaik sesuai batas kapasitas.

2. Tidak perlu mencoba semua kombinasi manual (hemat waktu & usaha).

3. Fleksibel: jika bobot/nilai/kapasitas berubah, algoritma tetap sama.

b. Jika input berubah

1. Misalnya kapasitas tas diubah menjadi 6 kg, hasil pilihan juga berubah (misalnya kombinasi (B1,B2,B3) bobot 6kg, nilai 11).

2. Prosedurnya tetap sama, hanya data input yang berubah.

3. Algoritma Adil dan Transparan

Algoritma Knapsack bersifat adil karena semua buku dipertimbangkan dengan kriteria bobot dan nilai, tidak ada yang diabaikan hanya karena ukurannya. Selain itu, algoritma ini transparan karena alasan pemilihan bisa dijelaskan dengan jelas, misalnya kombinasi B2 dan B3 dipilih karena memberi nilai tertinggi tanpa melebihi kapasitas. Dengan begitu, keputusan menjadi objektif, terbuka, efektif, efisien, dan mudah dipahami.