Belajar DP (Dynamic Programming) with C++ yukk…

Apa tuch DP? definisinya bisa liat di wikipedia, dsb.

dari wikipedia (English) : DP is In mathematics and computer science, dynamic programming is a method of solving problems exhibiting the properties of overlapping subproblems and optimal substructure (described below) that takes much less time than naive methods. Tapi yang pasti dalam algo ni kita harus mencari state dari masalah yang kita hadapi untuk menyelesaikan permasalahan tersebut.
DP tuch pendekatannya ada 2 jenis :
1.iteratif (bottom up)
2.rekursif (top down)

sebagai contoh, kita akan membuat algo DP utk fibonacci,
contoh fibonacci :
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946…
sebelumnya, bilangan fibonacci tuch secara matematika punya state sbb:
F(n) = F(n-1)+F(n-2) jika n>=2
F(n) = 0 jika n=0, atau F(0) = 0
F(n) = 1 jika n=1, atau F(1) = 1
so, F(2) = F(1) + F(0) = 0 + 1 = 1, F(3) = F(2) + F(1) = 1+1 = 2, dst

ada banyak cara membuat program fibonacci spt ini,
#include <stdio.h>
#define MAX 20 // kita mengeset nilai MAXnya yaitu 20
int memo[MAX]; // array untuk mnyimpan perhitungan sebelumnya
/* paling lambat (tanpa DP), karena ada perhitungan yang tidak dibutuhkan yang berulang*/
int Non_DP(int n) {
if (n==1 || n==2)
return 1;
else
return Non_DP(n-1) + Non_DP(n-2);
}
// top down DP
int DP_Top_Down(int n) {
// case dasar
if (n == 1 || n == 2)
return 1;
// jika tidak 0, maka akan menghasilkan nilai sebelumnya
if (memo[n] != 0)
return memo[n];
// selain itu, jika 0 maka lakukan sama dengan algo Non DP
memo[n] = DP_Top_Down(n-1) + DP_Top_Down(n-2);
return memo[n];
}
// DP, paling cepat, bottom up, menyimpan nilai sebelumnya di array
int DP_Bottom_Up(int n) {
memo[1] = memo[2] = 1; // value default untuk algo DP
// dari 3 ke n (kita sama2 tahu bahwa fib(1) and fib(2) = 1
for (int i=3; i<=n; i++)
memo[i] = memo[i-1] + memo[i-2];
return memo[n];
}

void main() {
int z;
// ini paling lambat (Non DP)
for (z=1; z<MAX; z++) printf(“%d-“,Non_DP(z));
printf(“\n\n”);
// ini lebih cepat dari yang pertama
for (z=0; z<MAX; z++) memo[z] = 0;
for (z=1; z<MAX; z++) printf(“%d-“,DP_Top_Down(z));
printf(“\n\n”);
/* secara normal algo ini paling cepat*/
for (z=0; z<MAX; z++) memo[z] = 0;
for (z=1; z<MAX; z++) printf(“%d-“,DP_Bottom_Up(z));
printf(“\n\n”);
}

explanation are :
1. utk algo non DP : ini paling lambat karena akan ada perhitungan yang berulang dihitung kembali, sebagai contoh dlm algo diatas adalah menampilkan bilangan fibonacci atau F(n) dari n=1 ke 19, utk F(3) dia akan langsung ketemu yaitu F(3) = F(2) + F(1) = 1 + 1=2, tapi utk n>3, maka akan ada perhitungan yang berulang yaitu sbg contoh : F(4) = F(3) + F(2), karena ini hanya algo fibonacci rekursif non DP, maka tidak ada penyimpanan terhadap perhitungan sebelumnya, yaitu F(3) tidak disimpan (dlm contoh algo DP, hasil disimpan di array), maka akan terjadi pengulangan perhitungan, yaitu : F(4) = (F(2) + F(1)) + F(2) = (1+1) + 1 = 2 + 1 = 3, coba lihat, prosesnya lebih banyak kan…karena algo NonDP ini akan menghitung lagi dari F(3), padahal pada proses sebelumnya sudah dihitung,
2. Top Down : (lanjut penjelasan dari algo Non DP) utk Top Down, perhitungan sebelumnya akan disimpan di array, yaitu saat F(3) sudah dihitung, maka hasilnya disimpan di array(contoh:Memo), jadi saat kita memanggil lagi F(3), tidak perlu dihitung lagi…yaitu dalam hal ini, utk pertama kali, array Memo di inisialisasi nilainya dengan 0, saat sudah dilakukan perhitungan maka dalam array tsb. tidak akan 0 lagi kan…F(3) = 2, maka Memo[3]=2 bukan 0, saat F(3) dipanggil lagi (misal saat F(4) = F(3)+F(2)), maka tidak perlu dihitung lagi cukup cek apakah Memo[n] adalah 0 atau tidak, jika bukan 0, maka pakai saja nilai yang ada d dalam array Memo, jadi secara otomatis saat F(4) = F(3) + F(2), akan langsung terhitung yaitu F(4) = 2+1 = 3, tidak perlu lagi dipecah (penghitungan ulang terhadap F(3)) atau F(4) = (1+1) + 1.
3. Bottom Up : pendekatan iteratif, why always the fastest? silahkan analizis sendiri😀, ini model generate value, pertama diberi inisialisasi awal bahwa Memo[1] = Memo[2] = 1, (dari rumus F(1) = 1, dan F(2) = 1), dan mulailah mengconstruct valuenya mulai dari n=3 ke n yang diinginkan yaitu dengan Memo[n] = Memo[n-1] + Memo[n-2]; saat n=3, maka Memo[3] = Memo[2] + Memo[1] (karena Memo[1] = Memo[2] = 1) maka Memo[3] = 1 +1 = 2, utk Memo[4] = Memo[3]+Memo[2] = 2 + 1 = 3, (lho koq langsung ketahuan nilai dari Memo[3]? karena pada algo ini langsung bermain ke arraynya / memoization), ya inilah yang menyebabkan algo ini paling cepat, tidak perlu me-rekursif ke bawah (Top Down / dari n yang diinginkan ke n=1 || n=2), karena sudah disimpan, dan polanya akan menghitung / men-construct value dari bawah ke atas (Bottom up).
GImana? bingung yach? atau puzziingg….yach kalo kata dosen Q, puzing karena berpikir itu baik, asalkan ga’ berpikir yg negatif lho..
Why we must learn this algorithms,because almost of problems in this world is like DP😀 kita harus tahu state solusinya terlebih dahulu dalam problem tersebut,sebelum solve !! saat kamu mendapat statenya, maka you’ve got AC!! yeach AC!! go..go..AC!! semisal dari problem fibonacci, kita harus tahu state dari fibonacci, yaitu fibonacci memiliki state
F(n)=F(n-1)+F(n-2), if n>=2 atau dalam algo yg kubuat tuch F(n)=F(n-1)+F(n-2), if n>=3, karena n=0 biasanya jarang disebut…hehe..met learn…n keep share knowledge, because knowledge is power!!

6 Responses so far »

  1. 1

    Felix J said,

    bottom up mu itu tidak efisien… ketika awalnya kupanggil fib 20.. maka kamu calculate kan dari awal? skarang kalo aku panggil fib 50, maka kamu akan ttp menghitung lagi dari fib 0 sampe fib 20.. padahal tinggal melanjutkan dari fib 20 ke atas… so? dimana lebih cpatnya?😛

    btw, pengertianmu ttg DP bottom up sepertinya masih salah..

  2. 2

    brainplusplus said,

    @felix j :
    kamu bener…bottom up gak efisien…kalo kondisinya kayak gtu…tapi, ada revisi source code untuk membuatnya efisien…
    yakni :
    int DP_Bottom_Up(int n) {
    memo[1] = memo[2] = 1;
    if(memo[n]!=0) return memo[n]; //tambahan source code agar lebih efisien
    for (int i=3; i<=n; i++)
    memo[i] = memo[i-1] + memo[i-2];
    return memo[n];
    }

  3. 3

    Felix J said,

    Bgini kalo saya tambahkan, Bottom Up itu biasanya disebut table lookup. Jadi, smua nilai yang ada didalam tabel itu, di-precompute terlebih dahulu. sehingga pada saat diprint hanya tinggal memanggil

    printf(“%d”, dp[x]);

    sedangkan top down, (biasanya/umumnya) dia menggunakan fungsi return value. jadi untuk kasus DP top down, biasanya seperti ini

    printf(“%d”, dp(x));

    dimana dp adalah fungsi untuk return nilai yang didapatkan setelah di DP.

    Untuk beberapa soal, DP Top Down malah lebih efisien (contoh: Salah Satu Soal ACM/ICPC Jakarta kmrn), ketimbang bottom upnya. Jadi tidak selalu DP bottom up lebih kenceng. ^^

    CMIIW

  4. 4

    elmatruder said,

    kirain gw DP = DISTURBING PICTURE

  5. 5

    JJ Black said,

    klo g salah istilah top down itu bukannya istilah divide n conquer (dnc)??

  6. 6

    brainplusplus said,

    @JJ : yup…top down adlh salah satu implementasi dr dnc, hm..biasany dgunakan dlm DP(Dynamic Programming)


Comment RSS · TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: