Page 255 - Modul Ajar Informatika SMA XII

terkait dengan permasalahan knapsack untuk menguji pemahaman mereka, serta kemampuan
mereka untuk menyelesaikan beberapa kasus permasalahan knapsack yang sederhana
(berukuran kecil), meskipun mungkin belum menemukan sebuah algoritma generik yang dapat
diterapkan untuk menyelesaikan semua kasus permasalahan knapsack.

Pembahasan dan Jawaban Aktivitas

(SAP-K11-18-U) Aktivitas PLB: Memahami Permasalahan Knapsack
1. Knapsack adalah permasalahan optimasi mencari maksimum, yaitu total nilai barang yang
terbesar yang dapat dimasukkan ke dalam wadah.
2. Fungsi tujuan dari optimasi pada permasalahan knapsack adalah total nilai barang yang
dimasukkan ke dalam wadah.
3. Kendala optimasi pada permasalahan knapsack adalah kapasitas wadah.
4. Jawaban:

a. Mengambil barang-barang B, D, E dan F tidak diperbolehkan sebagai solusi, karena total
bobot yang dihasilkan adalah 8 + 4 + 10 + 8 > 24.
b. Mengambil A, D, E saja diperbolehkan karena total bobot yang didapatkan adalah 3 + 4 +
10 = 17 < 24. Namun, nilai fungsi tujuannya disini (yaitu 6 + 6 + 5 = 17) masih belum
optimal, karena kita dapat memilih misalnya A, D dan F, dengan total bobot 3 + 4 + 8 =
15 < 24, dan total nilai = 6 + 6 + 10 = 22 > 17.
5. Untuk variasi permasalahan rational knapsack, sebagaimana yang akan dipelajari nanti,
solusi dari permasalahan dapat diperoleh dengan menerapkan strategi greedy yaitu dengan
memilih barang-barang dengan rasio nilai terhadap bobot yang terbesar terlebih dahulu.
Tabel berikut menunjukkan proses ini:

Jika diurutkan berdasarkan rasio nilai/bobot dari yang terbesar menuju ke yang terkecil,
urutan barang adalah: A, D, F, C, B dan E. Kita berturut- turut mengambil barang
berdasarkan urutan prioritas ini. Sampai dengan barang C, kita telah memperoleh total bobot
= 20 kg, dan total nilai = 27. Karena kapasitas wadah hanya 24 kg, kita tidak dapat
mengambil seluruh barang B yang berbobot 8 kg. Karena kita tinggal memiliki sisa
kapasitas wadah 4 kg lagi, maka berarti kita hanya dapat mengambil 0.5 bagian dari barang
B, untuk mendapatkan nilai sebanyak 0.5 * 4 = 2. Jadi total nilai maksimal yang dapat kita
kumpulkan adalah 27 + 2 = 29.

6. Pada variasi 0-1 knapsack, pilihan optimal didapatkan dengan memilih barang-barang A, D,
F, dan C (dengan total bobot = 20 kg) dan total nilai = 27.
Pada aktivitas ini, peserta didik diminta untuk memahami dan menggunakan sebuah skema
pengkodean permasalahan knapsack. Tugas mereka adalah pertama menjawab pertanyaan-
pertanyaan yang diberikan pada Buku Siswa tentang skema pengkodean permasalahan
knapsack, dan menuliskan jawabannya pada lembar kerja (analisis mereka). Kedua, mereka
harus membuat sebuah program (dalam bahasa C/C++) yang membaca masukan berupa
sebuah skema permasalahan knapsack dan kemudian menampilkan kembali deskripsi
permasalahan tersebut sebagai keluaran.

(SAP-K11-19) Aktivitas PLB: Mengkodekan Permasalahan Knapsack