Tag: knapsack

Knapsack Problem

Knapsack Problem

 Hai presser, jumpa lagi dengan postinganku. Nah, di postingan sebelumnya kita kan udah bahas secara singkat tentang dasar Dynamic Programming yaitu Tukar Koin (Coin Exchange) nih. Sekarang aku bakal sharing sedikit tentang contoh problem dalam Dynamic Programming. Lebih spesialnya adalah Knapsack Problem. Oke let’s go.

Problem :

 Di sebuah rumah terdapat N macam barang. Setiap barang memiliki berat dan harga masing-masing. Barang ke-i memiliki berat (Bi) dan memiliki harga (Hi). Pada suatu hari ada perampok yang datang di rumah tersebut dengan membawa karung yang mampu menampung barang sebanyak W kg. Berapakah keuntungan maksimal mungkin yang didapatkan ?

Review Permasalahan Rekursif :

 Misal kita memiliki karung berkapasitas 7 kg. Ketika memilih suatu barang yang berbobot 3 kg maka kapasitas tas kita akan tersisa 4 kg.Dengan ini kita mendapatkan subpersoalan yang sama yaitu dengan sisa kapasitas yang tersisa kita harus menemukan langkah-langkah pengambilan yang menguntungkan. Maka dari itu kitadapat menyelesaikan persoalan ini dengan rekursif.

Algoritma :

  1. Anggap saja kita memiliki fungsi g(x,y) yang dapat menghasilkan nilai maksimal dari barang yang telah diambil oleh perampok dimana X merupakan barang yang akan diambil/tidak dan Y merupakan sisa kapasitas karung yang dimiliki
  2. Jika barang tidak muat untuk diambil atau (Bx > Y ) maka tidak perlu dipilih atau g(x,y) = g(x-1,y)
  3. Jika barang masih muat untuk diambil maka bandingkan manakah yang lebih menguntungkan, ambil barang atau tidak –> g(x,y) = max ( g(x-1,y-berat[x])+harga[x], g(x-1,y))
  4. Base casenya ialah ketika barangnya habis atau x=0

Pseudocode:

   int g(int x,int y)
      if x==0 return 0;
      else if( y< berat[x] ) return g(x-1,y);
      else
         return max(g(x-1,y-berat[x])+harga[x],g(x-1,y));

Gimana presser? ternyata nggak terlalu sulit kan. Oke mungkin kali ini cuma itu yang bisa ku sharingkan. Semoga Bermanfaat dan Sampai Jumpa!!!