Tag: Dynamic Programming

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!!!

Advertisements
Problem Tukar Koin (Coin Exchange with Dynamic Programming Part 1)

Problem Tukar Koin (Coin Exchange with Dynamic Programming Part 1)

  Hai Presser, jumpa lagi dengan postinganku. Pada bahasan kali ini aku bakal sharing sedikit tentang salah satu dasar Dynamic Programming nih presser (meskipun masih newbie sih) . Oke kita mulai ya!!

  Dynamic Programming merupakan suatu strategi algoritma yang mungkin lebih identik dengan rekursi dan memoization (pencatatan). Selain itu, Dynamic Programming juga memiliki dua cara pendekatan, yaitu Top Down dan Bottom Up. Sebenarnya Problem Tukar Koin ini juga dapat diselesaikan dengan cara Brute Force namun pada part 1 ini aku bakal kasih sedikit solusi dengan menggunakan Rekursi tanpa memoization.

Problem :
  Si Elang memiliki coin 1, 3, 5 ia ingin pergi ke alphamaret untuk membeli sebuah daging. Harga daging tersebut adalah 12 rupiah. Berapakah banyaknya coin minimum yang harus dibawa oleh Elang?

Algoritma
-> Ketika kita pilih salah satu koin (Cx) maka kebutuhan kita menjadi N-Cx dan pada saat itu juga kita catat banyak coinnya.
-> Anggap kita mempunyai sebuah fungsi yang mencari nilai minimum dari pemilihan kita
-> Setiap pemilihan kita tambahkan banyaknya koin “f(N-Cx)+1” dan bandingkan manakah yang lebih kecil.

Pseudocode

 int exchange(int n)
   if(n==0) return 0;
   else
     int best=100000;
     for i= 1 to banyakCoin 
       if(C[i]<=n)
        best= min(best,exchange(n-C[i])+1);
    return best

Oke presser, mungkin untuk kali ini cuma itu yang dapat aku sharingkan. Terima kasih dan Sampai jumpa ya!!!!