Page 88 - Informatika-BS-KLS-XI
P. 88
nilai minimum eterkecilf. Fungsi tujuannya adalah banyaknya
pecahan uang yang harus dikumpulkan, sedangkan kendala yang
diberikan adalah besaran-besaran pecahan uang yang tersedia,
serta jumlah total besaran nilai uang yang harus dikumpulkan.
Pada PLB ini kita akan mempelajari bagaimana
menyelesaikan permasalahan yang biasa disebut sebagai
knapsack problem. Berikut ini adalah deskripsi umum
permasalahan knapsack problem.
Terdapat beberapa buah barang yang dapat kita ambil.
Setiap barang memiliki dua hal: bobot dan nilai. Kita diberikan
sebuah wadah yang dapat menampung beberapa buah barang,
namun kapasitasnya berat beban yang dapat ditampungnya
terbatas sampai suatu nilai tertentu (tidak boleh mengisi
wadah melebih bat maksimal kapasit beb ini, namu
tentuny boleh kurangf. Pertanyaanny adalah: “Dapatkah
kita memilih barang-barang yang diambil untuk dimasukkan
ke dalam wadah, sedemikian rupa sehingga kita mendapatkan
total nilai yang sebesar-besarnya, namun tidak melewati batas
maksimal beban wadah tersebut?”
Sebagai contoh, perhatikanlah kasus berikut ini. Misalnya kita
memiliki buah barang, sebut saja namanya A, B, C, D dan E,
dengan bobot edalam kgf dan nilai masing-masing sebagai berikut:
T Tabel 2.18 Keterangan Bobot dan Nilai dari 5 Barang (Knapsack Problem) Kasus 1
Barang A B C D E
Bobot 5 4 7 8 10
Nilai 10 5 7 12 8
Misalkan kapasitas maksimal dari wadah adalah kg.
Maka kita dapat melakukan beberapa contoh pilihan sebagai
berikut:
• Ambil barang A, B dan D. Total bobot yang harus
ditampung pada wadah adalah Ê Ê Ï kg, yang
Bab 2 Strategi Algoritmik dan Pemrograman 87
