Kunci Jawaban Informatika Kelas 11 Aktivitas SAP-K11-18-U: Memahami Permasalahan Knapsack

Kunci Jawaban Informatika Kelas 11 Aktivitas SAP-K11-18-U: Memahami Permasalahan Knapsack – Halo sobat, pada kesempatan ini akan dibahas tentang aktivitas memahami permasalahan knapsack. Di mana kalian akan berlatih tentang materi tersebut dengan menjawab soal menggunakan strategi  greedy. Pembahasan soal ini terdapat pada buku Informatika SMA Kelas XI Kurikulum Merdeka. Untuk penjelasan selengkapnya, mari kita simak bersama ulasan berikut ini !

Kunci Jawaban Informatika Kelas 11 Aktivitas SAP-K11-18-U: Memahami Permasalahan Knapsack Halaman 90

Aktivitas Berpasangan

Aktivitas SAP-K11-18-U: Memahami Permasalahan Knapsack

Jawablah pertanyaan-pertanyaan berikut dan tuliskan dalam laporan analisis.

1. Apakah jenis optimasi pada permasalahan knapsack? Apakah mencari minimum, ataukah maksimum? Jelaskan!

2. Tentukan apa yang menjadi fungsi tujuan dari permasalahan knapsack!

3. Tentukan apa yang menjadi kendala pada optimasi untuk permasalahan knapsack!

4. Perhatikan permasalahan knapsack yang ditunjukkan oleh Tabel 2.20 berikut. Diberikan 6 buah barang, A, B, s/d F dengan bobot dan nilai sebagai berikut:

Asumsikan bahwa tas memiliki kapasitas maksimal = 24 kg.

Baca Juga : Kunci Jawaban Informatika Kelas 8 Asesmen BAB 7 Algoritma Dan Pemrograman

a. Apakah pilihan mengambil barang-barang B, D, E dan F diperbolehkan sebagai solusi sesuai dengan kendala optimasi pada permasalahan tersebut? Mengapa?

b. Apakah pilihan mengambil barang-barang A, D, E diperbolehkan sebagai solusi sesuai dengan kendala optimasi pada permasalahan tersebut? Apakah fungsi tujuan mencapai nilai optimal dengan memilih A, D dan E saja? Mengapa?

5. Tentukan jawaban permasalahan knapsack tersebut pada soal no. 4, jika menggunakan variasi permasalahan rational knapsack!

6. Pada soal no. 4, apakah solusinya, jika digunakan variasi 0-1 knapsack? Apakah sama dengan solusi untuk variasi rational knapsack?

Jawaban :

1. Jenis optimasi pada permasalahan knapsack adalah permasalahan optimasi mencari maksimum, yaitu total nilai barang yang terbesar yang dapat dimasukkan ke dalam wadah.

2. Yang menjadi fungsi tujuan dari optimasi pada permasalahan knapsack adalah total nilai barang yang dimasukkan ke dalam wadah.

3. Yang menjadi kendala optimasi pada permasalahan knapsack adalah kapasitas wadah.

4. a. Pilihan mengambil barang-barang B, D, E dan F tidak diperbolehkan sebagai solusi, karena total bobot yang dihasilkan adalah 8 + 4 + 10 + 8 > 24.

b. Pilihan mengambil barang-barang 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. Jika menggunakan variasi permasalahan rational knapsack, sebagai solusi dari permasalahan kita dapat menerapkan strategi greedy yaitu dengan memilih barang-barang dengan rasio nilai terhadap bobot yang terbesar terlebih dahulu. Seperti berikut :

Baca Juga : Kunci Jawaban Informatika Kelas 7 Aktivitas SK-K7-07-U: Permasalahan pada Perangkat Keras

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.

Kesimpulan

Demikianlah pembahasan soal yang dapat disajikan tentang Kunci Jawaban Informatika Kelas 11 Aktivitas SAP-K11-18-U: Memahami Permasalahan Knapsack. Semoga artikel ini dapat bermanfaat, selamat belajar !

Baca Juga : Kunci Jawaban Informatika Kelas 8 Aktivitas AD-K8-06 Mengelola Data dengan Tables Halaman 160

Disclaimer :

1. Kunci jawaban pada artikel ini mungkin akan berbeda dengan jawaban sumber lain.
2. Jadikan kunci jawaban ini sebagai salah satu bahan referensi dalam menjawab soal bukan sebagai acuan utama dan satu-satunya.
3. Kunci jawaban ini tidak mutlak kebenarannya.