Permasalahan Knapsack 4


Permasalahan Knapsack salah satu permasalahan optimasi. Bagaimana caranya seseorang dapat membawa sejumlah barang yang tidak melebihi kapasitas, tetapi dengan nilai barang yang paling tinggi.
Contoh kasus adalah sebagai berikut. Ada seseorang yang ingin berwisata ke gunung, sedangkan dia hanya dapat membawa sebuah ransel yang isinya terbatas. Diantara barang-barang yang perlu dibawa seperti baju, celana, handuk, jaket, kamera, kaos kaki, kompas, peta, sarung tangan, senter; masing-masing memiliki berat dan nilai prioritas. Sehingga barang-barang mana saja yang harus dibawa masuk ke dalam ransel dengan berat yang tidak melewati kapasitas ransel tetapi dengan nilai barang yang paling tinggi.



ada tiga variasi dasar dari permasalahan knapsack, yaitu

  • UKP (Unbounded Knapsack Problem)
  • Dalam variasi ini, semua benda diasumsikan memiliki jumlah tidak terbatas, sehingga sebuah barang dapat dimasukkan ke dalam ransel dengan jumlah berapapun selama masih memenuhi batas kapasitas ransel

  • 0/1 (0/1 Knapsack Problem)
  • Dalam variasi ini, semua benda diasumsikan memiliki jumlah 1, sehingga perhitungan yang dilakukan akan menentukan sebuah barang masuk / tidak masuk ke dalam ransel

  • BKP (Bounded Knapsack Problem)
  • Dalam variasi ini, semua benda diasumsikan memiliki batas jumlah sendiri-sendiri, sehingga sebuah barang yang masuk ke dalam ransel harus memenuhi batas jumlah tersebut



Dalam kehidupan nyata, kasus BKP (Bounded Knapsack Problem) adalah kasus yang paling nyata, sehingga paling banyak digunakan dalam bidang lain. Pada contoh kasus ini akan dibahas semua variasi dasar tersebut untuk mengetahui perbedaan perhitungan antara ketiga variasi dasar tersebut.
Perlu diketahui, untuk masing-masing variasi dasar dapat diselesaikan oleh beberapa cara, yaitu

  • Greedy Algorithm
  • Dynamic Programming
  • Dominance Relations

Sedangkan Greedy Algorithm sendiri memiliki 3 teknik perhitungan, yaitu

  • Berat Terendah
  • Prioritas barang yang dihitung terlebih dahulu adalah dengan berat terendah, sehingga lebih banyak barang akan dapat masuk ke dalam ransel

  • Nilai Tertinggi
  • Prioritas barang yang dihitung terlebih dahulu adalah dengan nilai tertinggi, sehingga barang-barang dengan nilai tertinggi akan masuk ke dalam ransel

  • Rasio Nilai/Berat
  • Nilai barang akan dinormalisasi dengan cara dibagi berat barang tersebut. Prioritas barang yang dihitung terlebih dahulu adalah dengan nilai rasio tertinggi, yaitu barang-barang yang cukup bernilai tinggi dengan berat yang cukup rendah

Pada contoh kasus ini tidak semuanya akan dihitung, tetapi hanya akan diambil teknik yang berbeda saja untuk menunjukkan cara teknik perhitungan yang dimaksud.



Diasumsikan ada 10 buku yang dapat dibawa ke dalam sebuah knapsack, yaitu buku A,B,C,D,E,F,G,H,I,J
masing-masing buku memiliki berat dan nilai sendiri-sendiri
Maka tentukan buku apa saja yang seharusnya dibawa dengan berat yang tidak melebihi kapasitas dan dengan nilai tertinggi


UKP (Unbounded Knapsack Problem)

Teknik yang digunakan adalah Greedy Algorithm dengan prioritas berdasarkan berat terendah
Semua buku tersebut diasumsikan tidak terbatas jumlahnya
Diasumsikan data buku yang tersedia adalah sebagai berikut

Nama Barang Berat Nilai Jumlah
Buku A 25 30 Tidak Terbatas
Buku B 27 20 Tidak Terbatas
Buku C 19 15 Tidak Terbatas
Buku D 33 35 Tidak Terbatas
Buku E 27 25 Tidak Terbatas
Buku F 29 40 Tidak Terbatas
Buku G 32 30 Tidak Terbatas
Buku H 38 50 Tidak Terbatas
Buku I 37 40 Tidak Terbatas
Buku J 21 20 Tidak Terbatas

Contoh data buku tersebut adalah sebagai berikut:

* Agar dapat menjalankan skrip diatas, maka diperlukan sebuah Class UnboundedBarang untuk menampung semua data barang seperti nama, berat, nilai, dan batas jumlah sebuah barang. Deklarasi Class UnboundedBarang adalah sebagai berikut:



Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan kapasitas knapsack yang ada
Diasumsikan dalam kasus ini, kapasitas knapsack adalah 100 satuan


Langkah-langkah penggunaan algoritma ini adalah

1. Lakukan pengurutan barang dari berat terendah ke berat tertinggi
Skrip pengurutan sudah terdapat dalam skrip Class unboundedBarang diatas

2. Lakukan perulangan pada semua barang (poin 2a – 2c)

2a. Tentukan jumlah Barang, yaitu = sisa kapasitas / berat barang

2b. Catat total berat, yaitu berat barang * jumlah Barang

2c. Apabila total berat masih kurang dari kapasitas,
maka masukkan Barang ini sejumlah jumlah Barang ke dalam hasil jawaban
Kemudian catat total berat dan total nilai yang sudah dikumpulkan

3. Tampilkan hasil perhitungan akhir pada layar


0/1 (0/1 Knapsack Problem)

Teknik yang digunakan adalah Greedy Algorithm dengan prioritas berdasarkan nilai tertinggi
Semua buku tersebut diasumsikan hanya memiliki jumlah 1 buah
Diasumsikan data buku yang tersedia adalah sebagai berikut

Nama Barang Berat Nilai Jumlah
Buku A 25 30 1
Buku B 27 20 1
Buku C 19 15 1
Buku D 33 35 1
Buku E 27 25 1
Buku F 29 40 1
Buku G 32 30 1
Buku H 38 50 1
Buku I 37 40 1
Buku J 21 20 1

Contoh data buku tersebut adalah sebagai berikut:

* Agar dapat menjalankan skrip diatas, maka diperlukan sebuah Class nolSatuBarang untuk menampung semua data barang seperti nama, berat, nilai, dan batas jumlah sebuah barang. Deklarasi Class nolSatuBarang adalah sebagai berikut:



Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan kapasitas knapsack yang ada
Diasumsikan dalam kasus ini, kapasitas knapsack adalah 100 satuan


Langkah-langkah penggunaan algoritma ini adalah

1. Lakukan pengurutan barang dari nilai tertinggi ke nilai terendah
Skrip pengurutan sudah terdapat dalam skrip Class nolSatuBarang diatas

2. Lakukan perulangan pada semua barang (poin 2a – 2c)

2a. Tentukan jumlah Barang, yaitu = 1

2b. Catat total berat, yaitu berat barang * jumlah Barang

2c. Apabila total berat masih kurang dari kapasitas,
maka masukkan Barang ini sejumlah jumlah Barang ke dalam hasil jawaban
Kemudian catat total berat dan total nilai yang sudah dikumpulkan

3. Tampilkan hasil perhitungan akhir pada layar


BKP (Bounded Knapsack Problem)

Teknik yang digunakan adalah Dynamic Programing
Semua buku tersebut diasumsikan memiliki batas jumlah sendiri-sendiri
Diasumsikan data buku yang tersedia adalah sebagai berikut

Nama Barang Berat Nilai Jumlah
Buku A 25 30 1
Buku B 27 20 2
Buku C 19 15 4
Buku D 33 35 3
Buku E 27 25 3
Buku F 29 40 2
Buku G 32 30 4
Buku H 38 50 1
Buku I 37 40 1
Buku J 21 20 2

Contoh data buku tersebut adalah sebagai berikut:

* Agar dapat menjalankan skrip diatas, maka diperlukan 2 Class yaitu Class BoundedBarang untuk menampung semua data barang seperti nama, berat, nilai, dan batas jumlah sebuah barang, dan Class daftarBoundedBarang untuk menampung semua jawaban barang beserta total berat dan total nilai. Deklarasi Class BoundedBarang dan Class daftarBoundedBarang adalah sebagai berikut:



Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan kapasitas knapsack yang ada
Diasumsikan dalam kasus ini, kapasitas knapsack adalah 100 satuan


Langkah-langkah penggunaan algoritma ini adalah

1. Lakukan perulangan untuk setiap kapasitas (j) pada semua barang (i)
Jika kapasitas ke j lebih dari berat barang ke i, maka lakukan perhitungan berikutnya

2. Tentukan jumlah Barang, yaitu = nilai minimal antara batas minimal setiap barang atau nilai kapasitas ke j / berat barang

3. Lakukan perulangan pada setiap jumlah Barang yang ditemukan (poin 3a – 3c)

3a. Catat barang pada kapasitas ke j – (jumlah Barang * berat barang)

3b. Catat akumulasi nilai, yaitu total nilai + (jumlah Barang * nilai barang)

3c. Apabila akumulasi nilai masih lebih dari total nilai,
maka masukkan Barang ini sejumlah jumlah Barang ke dalam hasil jawaban

4. Tampilkan hasil perhitungan akhir pada layar


Hasil akhir untuk ketiga variasi permasalahan diatas adalah: (klik untuk perbesar gambar)

cmd64


Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:



Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.


Tinggalkan sebuah komentar

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *

4 pemikiran di “Permasalahan Knapsack

  • Malaikhah

    Boleh tau referensi dalam menulis postingan ini? Saya membutuhkan buku untuk mengetahui ttg rasio diatas untuk skripsi saya. Terimakasih

    • pip Penulis

      Saya hanya menggunakan referensi wikipedia yang dapat anda akses melalui halaman https://en.wikipedia.org/wiki/Knapsack_problem
      Dalam halaman tersebut pada bagian Dominance Relation dan sub bagian Modular Dominance terdapat kalimat yang intinya barang terbaik ditentukan dengan menggunakan rumus (vb / wb). Dengan kata lain (value b / weight b), atau diterjemahkan menjadi (nilai b / berat b). Inilah dasar nilai rasio yang saya gunakan dalam perhitungan diatas.

    • pip Penulis

      Saya tidak memiliki cara perhitungan manual untuk algoritma ini, tetapi konsep dari permasalahan knapsack cukup mudah sehingga perhitungannya dapat disusun secara manual setelah memahami konsep dari permasalahan tersebut.