Tentukan Jawaban Permasalahan Knapsack Tersebut pada Soal No. 4, Jika Menggunakan Variasi Permasalahan Rational Knapsack!
Tentukan jawaban permasalahan knapsack tersebut pada soal no. 4, jika menggunakan variasi permasalahan rational knapsack!
Jawaban:
Jawaban permasalahan knapsack tersebut pada soal no. 4, jika menggunakan variasi permasalahan rational knapsack adalah memasukkan barang A, D, C, dan B ke dalam tas dengan total bobot 20 kg dan total nilai 21.
Penjelasan:
Dalam permasalahan rational knapsack, selain mempertimbangkan bobot dan nilai suatu barang, kita juga memperhatikan rasio nilai per bobot (value-to-weight ratio) untuk memilih barang yang akan dimasukkan ke dalam tas. Tujuan utamanya adalah memaksimalkan nilai total barang yang dimasukkan ke dalam tas dengan mempertimbangkan keterbatasan kapasitas.
Dalam kasus ini, kita memiliki 6 barang dengan bobot dan nilai yang telah diberikan. Pertama, kita perlu menghitung rasio nilai per bobot untuk setiap barang. Rasio tersebut dapat dihitung dengan membagi nilai barang dengan bobot barang.
Berikut adalah perhitungan rasio nilai per bobot untuk setiap barang:
- Barang A: Rasio = 6/3 = 2
- Barang B: Rasio = 4/8 = 0.5
- Barang C: Rasio = 5/5 = 1
- Barang D: Rasio = 6/4 = 1.5
- Barang E: Rasio = 5/10 = 0.5
- Barang F: Rasio = 10/8 = 1.25
Setelah menghitung rasio nilai per bobot, kita dapat mulai memilih barang untuk dimasukkan ke dalam tas dengan mempertimbangkan kapasitas maksimal tas.
Langkah-langkah untuk menyelesaikan permasalahan knapsack dengan menggunakan variasi permasalahan rational knapsack:
1. Urutkan barang-barang berdasarkan rasio nilai per bobot dari yang tertinggi hingga terendah.
Urutan: A, D, F, C, E, B
2. Mulai dari barang dengan rasio tertinggi, masukkan barang tersebut ke dalam tas selama masih memungkinkan tanpa melebihi kapasitas maksimal tas.
a. Barang A: Bobot = 3, Nilai = 6 (Dimasukkan ke dalam tas)
b. Barang D: Bobot = 4, Nilai = 6 (Dimasukkan ke dalam tas)
c. Barang F: Bobot = 8, Nilai = 10 (Tidak dimasukkan ke dalam tas karena melebihi kapasitas)
3. Setelah mencoba semua barang, periksa apakah masih ada kapasitas yang tersisa dalam tas.
Kapasitas tersisa = Kapasitas maksimal - (Bobot Barang A + Bobot Barang D) = 24 - (3 + 4) = 17 kg
4. Jika masih ada kapasitas yang tersisa, periksa barang dengan rasio nilai per bobot tertinggi selanjutnya dan masukkan barang tersebut ke dalam tas jika memungkinkan.
a. Barang C: Bobot = 5, Nilai = 5 (Dimasukkan ke dalam tas)
b. Barang E: Bobot = 10, Nilai = 5 (Tidak dimasukkan ke dalam tas karena melebihi kapasitas)
5. Setelah mencoba semua barang, periksa kembali apakah masih ada kapasitas yang tersisa dalam tas.
Kapasitas tersisa = Kapasitas maksimal - (Bobot Barang A + Bobot Barang D + Bobot Barang C) = 24 - (3 + 4 + 5) = 12 kg
6. Jika masih ada kapasitas yang tersisa, periksa barang dengan rasio nilai per bobot tertinggi selanjutnya dan masukkan barang tersebut ke dalam tas jika memungkinkan.
a. Barang B: Bobot = 8, Nilai = 4 (Dimasukkan ke dalam tas)
Setelah mencoba semua barang, kapasitas tas telah terpenuhi atau tidak ada kapasitas tersisa.
Jawaban dari permasalahan knapsack dengan variasi permasalahan rational knapsack adalah:
Barang yang dimasukkan ke dalam tas:
- Barang A dengan bobot 3 kg dan nilai 6
- Barang D dengan bobot 4 kg dan nilai 6
- Barang C dengan bobot 5 kg dan nilai 5
- Barang B dengan bobot 8 kg dan nilai 4
Total bobot barang yang dimasukkan = 3 + 4 + 5 + 8 = 20 kg
Total nilai barang yang dimasukkan = 6 + 6 + 5 + 4 = 21
Sehingga, jawaban permasalahan knapsack tersebut dengan menggunakan variasi permasalahan rational knapsack adalah memasukkan barang A, D, C, dan B dengan total bobot 20 kg dan total nilai 21.