Baca tanpa iklan
Kunci Jawaban
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. a. Mengambil barang-barang B, D, E dan F tidak diperbolehkan seba- gai 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.
Jika diurutkan berdasarkan rasio nilai/bobot dari yang terbesar menuju nilai = 27.
Karena kapasitas wadah hanya 24 kg, kita tidak dapat meng ambil seluruh barang B yang berbobot 8 kg.
Karena kita tinggal memi liki sisa kapasitas wadah 4 kg lagi,
maka berarti kita hanya dapat meng ambil 0.5 bagian dari barang B, untuk mendapatkan nilai sebanyak 0. * 4 = 2.
Jadi total nilai maksimal yang dapat kita kumpulkan adalah 27 2 = 29.
6. Solusi 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.