Tag: tukar koin

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