Home » Kuliah IT » RPL » Algoritma Knapsack Problem

Algoritma Knapsack Problem

by marzuki
by marzuki

Apakah anda cukup familiar dengan knapsack? Ibaratnya knapsnack itu karung atau tas yang bisa difungsikan dalam menyimpan sesuatu. Namun, tidak semua jenis barang dapat dimasukkan ke dalamnya. Karung ini hanya bisa menyimpan objek-objek yang ukuran totalnya tidak melebihi kapasitas karung tersebut. Dari sini akan timbul permasalahan mengenai objek mana yang harus diutamakan untuk masuk ke dalam knapsack. Untuk lebih detailnya mengenai permasalahan tersebut beserta solusinya, simaklah uraian berikut ini.  (Baca juga : Pengertian Sistem Informasi Manajemen)

Permasalahan Algoritma Knapsack

Istilah lain yang masih ada sangkut pautnya yaitu knapsnack problem. Knapsnack problem adalah masalah yang mana seseorang berhadapan dengan persoalan optimasi pemilihan benda mana yang bisa ditampung ke dalam suatu wadah berkapasitas terbatas. Adapun optimasi dimaksudkan agar dalam proses pemilihan benda mana yang hendak dimasukkan ke dalam suatu wadah yang dimaksud dihasilkan keuntungan semaksimal mungkin. Masing-masing dari benda yang hendak dimasukkan ini berat dan nilainya difungsikan dalam menentukan prioritasnya pada pemilihan tersebut.

Adapun nilai yang dimaksud bisa berupa harga barang, tingkat kepentingan, nilai sejarah dan lain-lain. Untuk wadah dalam bahasan ini mempunyai nilai konstanta sebagai nilai pembatas terhadap tiap-tiap benda yang hendak dimasukkan ke dalam wadah yang tersedia itu. Dalam hal ini ada sebuah tuntutan untuk menggunakan sebuah metode memasukkan benda yang dimaksud tersebut ke dalam sebuah wadah agar menghasilkan hasil yang optimal tetapi tidak melampaui kemampuan wadahnya. (Baca juga : Fungsi Database)

Setelah mengetahui apa itu knapsnack problem, rasanya kurang lengkap jika tidak mengenal apa saja jenis-jenisnya. Jenis-jenis knapsnack problem bisa diamati dalam beberap variasi di antaranya:

  • 0/1 Knapack problem dimana tiap barang cuma tersedia sebanyak 1 unit, ambil atau lepaskan begitu saja.
  • Fracksional knapsack problem. Dalam hal ini barang bisa dibawa hanya sebagian. Jenis problem ini bisa masuk akal jika barang yang ada bisa dibagi-bagi seperti tepung, gula dan lain-lain.
  • Bounded Knapsack problem. Pada jenis ini, masing-masing barang tersedia tersedia dalam N unit yang mana jumlahnya terbatas.
  • Unbounded Knapshack problem. Untuk jenis Knapsack problem yang satu ini masing-masing barang yang tersedia jumlahnya minimal dua unit atau bahkan tak terbatas. (Baca juga : Karakteristik Sistem Informasi)

Pendekatan untuk Menyelesaikan Permasalahan Knapsack

Persoalan knapsack merupakan suatu persoalan yang cukup menarik untuk diamati. Dalam kehidupan masalah knapsack kerap kali dijumpai pada bidang tertentu seperti pengangkutan barang (termasuk pengangkutan peti dalam kapal). Untuk urusan ini diharapkan adanya keuntungan maksimal yang diraih dalam usaha pengangkutan barang tersebut tanpa melebihi kapasitas yang tersedia. Maka dari itu, sebuah solusi sangat diharapkan mampu menyelesaikan persoalan tersebut. Sebagaimana diketahui, problem knapsack merupakan permasalahan pada optimasi kombinatorial yang mana anda harus menemukan solusi terbaik dari berbagai kemungkinan yang ada. Strategi yang diharapkan berperan dalam penuntasan masalah tersebut di antaranya sebagai berikut : (Baca juga : Pengertian Sistem Basis Data Terdistribusi)

  • Brutal force

Brutal  force merupakan pendekatan straightforward guna menyelesaikan masalah yang mana begitu bergantung pada definisi atas suatu konsep dana pernyataan masalah. Jika ada n item sebagai pilihannya, akan muncul 2 kemungkinan kombinasi yang dihasilkan item-item tersebut supaya diletakkan di knapsack. Dalam hal ini sebuah item bisa saja terpilih ataupun tidak terplih berdasarkan kombinasi tersebut. Selanjutnya, baik angka 0 maupun angka q akan dihidupkan sepanjang n. Apabila I menunjukkan angka itu artinya item demikian tidak terpilih sedangkan apabila angka 1, itu artinya item yang dimaksud dipilih. (Baca juga : Kelebihan dan Kekurangan Sistem Basis Data Terdistribusi)

  • Algoritma Greedy

Selanjutnya, terdapat Algoritma Greedy yang merupakan teknik pemrograman yang kerap kali digunakan dalam mengatasi permasalahan optimasi. Cara kerja algoritma ini yaitu dengan menggunakan heuristic dalam mencari sebuah solusi suboptimum dengan harapan solusi optimum. Algoritma Greedy ini memiliki tiga strategi dalam memilih objek mana yang hendak dimasukkan ke dalam wadah yang bernama knapsack. Ketiga strategi tersebut antara lain sebagai berikut.  (Baca juga : Pengertian Algoritma, Flowchart dan Pseudo)

  1. Algoritma Greedy by weight – Strategi ini menekankan pada bobot yang paling ringan dalam memasukkan suatu objek. Strategi ini berusaha memaksimalkan keuntungan dari banyaknya objek yang masuk. Dengan kata lain keuntungan akan diperoleh jika objek dimasukkan sebanyak mungkin ke dalam wadah knapsack. Mekanismenya dimulai dengan mengurutkan ke atas objek-objek yang dimaksud dengan mendasarkan pada beratnya. Berikutnya satu demi satu objek diambil hingga tak ada satu pun objek yang dapat dimasukkan atau algoritma knapsack penuh.  (Baca juga : Macam-macam Bahasa Pemrograman)
  2. Algoritma Greedy by profit – Teknik ini menekankan pada objek dengan keuntungan yang besar sebagai pengisi knapsack. Bisa dikatakan bahawa strategi ini berusaha memaksimalkan keuntungan dengan cara mendahulukan yang paling menguntungkan dalam memenuhi space yang tersedia. Prosesnya diawali dengan mengurutkan ke bawah objek-objek dengan mendasarkan pada profitnya. Barulah kemudian satu demi satu objek yang masih dapat ditampung dimasukkan ke dalam knapsack hingga tak ada lagi objek yang dapat dimasukkan atau knapsack penuh. (Baca juga : Perbedaan Data dan Informasi)
  3. Untuk menuntaskan macam-macam strategi dalam algoritma Greedy, yang terakhir yaitu Greedy by density. Strategi ini menekankan pada objek-objek dengan densitas terbesar dalam memenuhi wadah yang tersedia. Strategi ini berusaha memaksimalkan keuntungan yang ada dengan cara memilih objek dengan keuntungan tiap unit berat yang paling bear. Mekanismenya diawali dengan mencari nilai keuntungan per unit atau densisiy atas masing-masing objek. Selanjutnya, objek-objek yang dimaksud diurutkan dari segi densitynya. Barulah satu demi satu dari objek yang masih dapat ditampung dimasukkan hingga penuh ke dalam knapsack. (Baca juga : Kelebihan Sistem Basis Data)

Setelah ketiga strategi yang telah disebutkan di atas diaplikasikan dan diuji, akan didapatkan hasil terbaik dengan menerapkan aturan ketiga, seperti memilih item yang memiliki nilai tinggi berdasarkan rasio bobot atas berat objek. Pemilihan objek yang didasarkan pada salah satu di antara ketiga strategi yang telah disebutkan sebelumnya memang tidak menjamin solusi optimal. Lain halnya dengan brutal force dimana strategi ini selalu mampu menghadirkan hasil optimal. Namun demikian, greedi mengurangi banyaknya langkah pencarian. (Baca juga Komponen Sistem Informasi)

You may also like