Pendahuluan
Knapsack problem adalah salah satu permasalahan yang sering dijumpai dalam ilmu komputer dan matematika terapan. Masalah ini dikenal sebagai permasalahan optimisasi, di mana kita harus memilih sejumlah item dengan nilai tertentu agar muatan yang dimasukkan ke dalam tas memiliki nilai maksimum. Dalam artikel ini, kami akan memberikan contoh soal knapsack problem beserta solusinya.
Deskripsi Soal
Misalkan kita memiliki sebuah tas dengan kapasitas W dan sejumlah item dengan bobot dan nilai yang berbeda-beda. Tugas kita adalah memilih item-item mana yang harus dimasukkan ke dalam tas sehingga total nilai yang dimiliki adalah maksimal.
Contoh soalnya adalah sebagai berikut:
Terdapat 5 item dengan bobot dan nilai sebagai berikut:
| Item | Bobot | Nilai |
|---|---|---|
| Item 1 | 2 | 5 |
| Item 2 | 3 | 8 |
| Item 3 | 4 | 9 |
| Item 4 | 5 | 10 |
| Item 5 | 9 | 15 |
Solusi
Untuk menyelesaikan masalah knapsack ini, kita dapat menggunakan pendekatan algoritma dinamis. Dalam algoritma dinamis, kita akan memecahkan masalah menjadi submasalah yang lebih kecil, kemudian menggabungkan solusi dari submasalah tersebut untuk mendapatkan solusi akhir.
Langkah-langkah untuk menyelesaikan contoh soal knapsack problem di atas adalah sebagai berikut:
Langkah 1: Membangun Tabel
Pertama, kita perlu membangun tabel yang berukuran (jumlah item + 1) x (kapasitas tas + 1). Tabel ini akan digunakan untuk menyimpan solusi dari submasalah yang lebih kecil.
Contoh tabel untuk soal di atas adalah sebagai berikut:
| Bobot/Nilai | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | – | – | – | – | – | – | – | – | – | – |
| 3 | 0 | – | – | – | – | – | – | – | – | – | – |
| 4 | 0 | – | – | – | – | – | – | – | – | – | – |
| 5 | 0 | – | – | – | – | – | – | – | – | – | – |
| 9 | 0 | – | – | – | – | – | – | – | – | – | – |
Langkah 2: Mengisi Nilai Tabel
Setelah tabel terbentuk, kita dapat mulai mengisi nilainya. Kita akan menggunakan rumus berikut untuk mengisi setiap sel dalam tabel:
tabel[i][j] = max(tabel[i-1][j], tabel[i-1][j-bobot] + nilai)
Dalam rumus di atas, i merupakan indeks item dan j merupakan kapasitas tas yang sedang dipertimbangkan.
Contoh isi tabel untuk soal di atas adalah sebagai berikut:
| Bobot/Nilai | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 |
| 3 | 0 | 0 | 5 | 8 | 8 | 8 | 8 | 8 | 8 | 8 | 8 |
| 4 | 0 | 0 | 5 | 8 | 9 | 9 | 9 | 9 | 9 | 9 | 9 |
| 5 | 0 | 0 | 5 | 8 | 9 | 10 | 10 | 10 | 10 | 10 | 10 |
| 9 | 0 | 0 | 5 | 8 | 9 | 10 | 10 | 10 | 10 | 10 | 15 |
Setelah tabel terisi, maka nilai maksimal yang dapat kita dapatkan adalah 15.
Kesimpulan
Contoh soal knapsack problem di atas mengilustrasikan bagaimana kita dapat menggunakan algoritma dinamis untuk menyelesaikan masalah optimisasi ini. Dengan membangun tabel dan mengisi nilainya, kita dapat menentukan kombinasi item yang harus dimasukkan ke dalam tas agar nilai totalnya maksimal.
Knapsack problem memiliki banyak aplikasi dalam kehidupan sehari-hari, seperti dalam perencanaan investasi, pengaturan jadwal, dan lainnya. Dengan memahami konsep dasar dari knapsack problem, kita dapat mengembangkan solusi yang lebih kompleks untuk masalah-masalah yang serupa.
Demikianlah contoh soal knapsack problem beserta solusinya. Semoga artikel ini dapat memberikan pemahaman yang lebih baik tentang konsep dan aplikasi dari knapsack problem.