Page 89 - Informatika-BS-KLS-XI
P. 89
masih di bawah maksimal kapasitas wadah. Total nilai
yang kita dapatkan adalah Ê Ê Ï .
• Ambil barang B, C dan D, dengan total bobot Ï Ê Ê Ï
kg, dengan total nilai yang didapatkan Ï Ê Ê Ï .
• Ambil barang A, C dan D, dengan total bobot Ï Ê Ê Ï
kg, dengan total nilai yang didapatkan Ï Ê Ê Ï .
Tentunya kita tidak dapat mengambil A, B, C dan D sekaligus
misalnya, karena total bobotnya adalah Ê Ê Ê Ï Õ kg,
sehingga akan melewati kapasitas dari wadah. Ternyata, nilai
total yang didapatkan dari memilih A, C dan D di atas
adalah nilai maksimal yang kita dapatkan, dan tidak ada
pemilihan pengambilan barang yang lain yang menghasilkan
nilai total Õ dengan tetap memenuhi persyaratan total
bobot Ô kapasitas.
2. Rational dan 0-1 Knapsack
Terdapat dua jenis variasi dari permasalahan knapsack. Yang
pertama adalah yang disebut sebagai rational knapsack. Pada
permasalahan ini, setiap barang dapat dianggap sebagai barang
dapat dipecah, artinya, boleh diambil sebagian saja etidak
harus semuanyaf. Contoh barang seperti ini adalah misalnya:
air, minyak, beras, pasir, dan lain-lain. Jika Anda memiliki
kg minyak, Anda dapat memilih untuk mengambil hanya
kg dari minyak tersebut, sehingga nilai yang Anda dapatkan
adalah / dari nilai total keseluruhan minyak. Karena
setiap barang sifatnya dapat dipecah dan diambil sebagian,
maka permasalahan rational knapsack biasanya lebih mudah
diselesaikan, karena kita dapat mengatur untuk setiap barang,
berapa bagian yang ingin kita ambil.
Variasi kedua dari permasalahan knapsack adalah yang
disebut sebagai −1 knapsack. Sesuai dengan namanya,
pada permasalahan −1 knapsack, kita hanya dapat memilih
untuk mengambil atau tidak mengambil setiap barang,
karena setiap barang sifatnya adalah tunggal dan tidak dapat
88 Informatika untuk SMA Kelas XI
