Pada Soal No. 4, Apakah Solusinya, Jika Digunakan Variasi 0-1 Knapsack?
Pada soal no. 4, apakah solusinya, jika digunakan variasi 0-1 knapsack? Apakah sama dengan solusi untuk variasi rational knapsack?
Jawaban:
Solusi untuk variasi 0-1 knapsack pada permasalahan ini adalah memilih barang A, B, C, D, dan F dengan total nilai 22 dan total bobot 23. Solusi untuk variasi rational knapsack mungkin berbeda, tetapi tanpa informasi tentang faktor skala rasional yang diberikan, tidak dapat dipastikan apakah solusinya akan sama atau berbeda.
Penjelasan:
Pada permasalahan knapsack di atas, jika digunakan variasi 0-1 knapsack, solusinya adalah sebagai berikut:
Dalam variasi 0-1 knapsack, setiap barang hanya bisa dipilih satu kali atau tidak dipilih sama sekali. Tujuan adalah memilih kombinasi barang yang memberikan total nilai maksimum tanpa melampaui kapasitas maksimal tas.
Dalam kasus ini, kita memiliki 6 barang dengan bobot dan nilai yang telah diberikan. Kita juga diberikan batasan berupa kapasitas maksimal tas sebesar 24 kg.
Untuk menyelesaikan masalah knapsack ini dengan variasi 0-1, kita dapat menggunakan pendekatan dynamic programming. Membangun tabel DP berukuran (jumlah barang + 1) × (kapasitas maksimal + 1) dan mengisi nilai-nilai di dalamnya berdasarkan hubungan rekursif.
Berikut adalah tabel DP yang dihasilkan:
| Barang | Kapasitas | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |
|:----------:|:---------:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
| - | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A(6) | 3 | 0 | 0 | 0 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 |
| B(4) | 8 | 0 | 0 | 0 | 6 | 6 | 6 | 6 | 6 | 6 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 | 10 |
| C(5) | 5 | 0 | 0 | 0 | 6 | 6 | 6 | 6 | 6 | 6 | 10 | 11 | 11 | 11 | 11 | 11 | 11 | 11 | 16 | 16 | 16 | 16 | 16 | 16 | 16 | 16 |
| D(6) | 4 | 0 | 0 | 0 | 6 | 6 | 6 | 6 | 12 | 12 | 12 | 12 | 17 | 17 | 17 | 17 | 17 | 17 | 17 | 22 | 22 | 22 | 22 | 22 | 22 | 22 |
| E(5) | 10 | 0 | 0 | 0 | 6 | 6 | 6 | 6 | 12 | 12 | 12 | 12 | 17 | 17 | 17 | 17 | 17 | 17 | 17 | 22 | 22 | 22 | 22 | 22 | 22 | 22 |
| F(10) | 8 | 0 | 0 | 0 | 6 | 6 | 6 | 6 | 12 | 12 | 12 | 12 | 17 | 17 | 17 | 17 | 17 | 17 | 17 | 22 | 22 | 22 | 22 | 22 | 22 | 22 |
Dalam tabel ini, setiap sel berisi nilai maksimum yang dapat dicapai pada titik tersebut. Nilai di sel (i, j) menunjukkan nilai maksimum yang dapat dicapai dengan mempertimbangkan barang-barang A hingga F hingga indeks ke-i (termasuk barang ke-i) dan dengan kapasitas maksimal j.
Setelah tabel DP selesai, nilai maksimum yang dapat dicapai adalah 22. Ini diperoleh ketika semua barang terpilih kecuali barang E dengan total bobot 23. Jadi, solusi untuk variasi 0-1 knapsack adalah memilih barang A, B, C, D, dan F dengan total nilai 22 dan total bobot 23.
Untuk variasi rational knapsack, solusinya mungkin berbeda. Pada variasi rational knapsack, setiap barang dapat dipilih sebagian berdasarkan faktor skala rasional. Dalam hal ini, kita tidak memiliki informasi tentang faktor skala rasional yang diberikan, jadi tidak dapat memastikan apakah solusinya akan sama atau berbeda dari variasi 0-1 knapsack.