Page 90 - Informatika-BS-KLS-XI
P. 90
dipecah belah. Contoh barang seperti ini adalah misalnya:
laptop, sepeda, mobil, hewan dan sebagainya, yang tentunya
tidak dapat diambil hanya sebagian/sepotong saja, dan kita
harus menentukan apakah setiap barang akan diambil atau
tidak. Permasalah - knapsack biasanya lebih sulit untuk
diselesaikan daripada rational knapsack.
Perhatikan contoh kasus berikut ini. Diberikan tiga buah
barang yang tidak dapat dibagi/dipecah, A, B dan C dengan
bobot dan nilai sebagai berikut yang akan ditaruh dalam
sebuah wadah.
T Tabel 2.19 Keterangan Bobot dan Nilai dari 3 Barang (Knapsack Problem) Kasus 2
Barang A B C
Bobot 5 4 7
Nilai 10 5 7
Misalkan bahwa kapasitas wadah adalah kg. Apabila kita
mengasumsikan bahwa jenis permasalahan ini adalah rational
knapsack, maka kita dapat mengambil solusi sebagai berikut:
• Ambil semua barang A, sehingga didapatkan bobot Ï
kg, total nilai sementara Ï .
• Kemudian ambil semua barang B, sehingga didapatkan
bobot Ï Ê Ï kg, dan nilai total sementara Ï Ê Ï .
• Ambil / bagian dari barang C, sehingga didapatkan
total bobot Ï Ê / q Ï kg, dan nilai total menjadi
Ê / q Ï .
Hasil ini ternyata adalah hasil yang maksimal, kita tidak
dapat memperoleh nilai total yang lebih besar dari tanpa
melebihi kapasitas wadah, yaitu kg.
Nah sekarang, seandainya kita menganggap permasalahan
ini sebagai permasalahan - knapsack, maka kita hanya
dapat mengambil setiap barang secara keseluruhan, atau tidak
sama sekali. Maka dalam kasus ini, solusi optimalnya adalah
Bab 2 Strategi Algoritmik dan Pemrograman 89
