Jawaban Informatika Kelas 11 SMA Hal 90 Aktivitas PLB, Aktivitas Berpasangan, Aktivitas SAP-K11-18-U

Kendala optimasi pada permasalahan knapsack adalah kapasitas wadah.

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:

Tabel 2.20 Keterangan Bobot dan Nilai dari 6 Barang (Knapsack Problem) Aktivitas PLB

Asumsikan bahwa tas memiliki kapasitas maksimal = 24 kg.

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

Jawaban :

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

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?

Jawaban :

Mengambil A, D, E saja diperbolehkan karena total bobot yang didapatkan adalah 3 + 4 + 10 = 17 < 24 xss=removed xss=removed xss=removed> 17.

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

Jawaban :

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 soal no. 4, apakah solusinya, jika digunakan variasi 0-1 knapsack? Apakah sama dengan solusi untuk variasi rational knapsack?

Jawaban :

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.

Dapatkan konten pendidikan mata pelajaran lainnya dari Kurikulum Merdeka dan Kurikulum 2013 dengan klik Di Sini.

Dapatkan juga berita penting dan informasi menarik lainnya dengan mengklik Google News.