Dynamic Programming 15

Apa itu Dynamic Programming ? Dynamic Programming (biasa disingkat DP) adalah suatu teknik algoritma untuk memecahkan masalah dimana solusi optimal dari masalah tersebut dapat dipandang sebagai suatu deret keputusan.

Halaman ini akan berisi kumpulan soal-soal Dynamic Programming(beserta clue) dan akan terus diupdate setiap saya menemukan soal-soal Dynamic Programming yang menarik :D.

Mohon tambahkan di bagian komentar apabila kalian menemukan soal-soal Dynamic Programming yang juga menarik untuk dikerjakan ^_^.

2262 – Bracket

Misalkan f(a,b) adalah cost terbaik dari sub-string yang dimulai dari posisi a dan diakhiri dengan posisi b. Yang kita ingin cari adalah f(0,N-1) dimana N adalah panjang string.

f(a,b) = 0, jika a>=b
f(a,b) = maximum( option1, option2) jika a < b
option1 = maximum( f(a,i) + f(i+1,b) ) untuk i=a sampai i=b-1.
option2 = 2 + f(a+1,b-1), jika karakter pada posisi a adalah pasangan karakter pada posisi b (Contoh: ‘[‘ dengan ‘]’ dan ‘(‘ dengan ‘)’ ).
option2 = 0, jika karakter pada posisi a bukan pasangan karakter pada posisi b.
Kompleksitas total adalah O(N^3).

bracket.jpg

1832 – Little Shop of Flowers

Misalkan f(a,b) adalah cost terbaik bila kita mulai dari bunch ke-a dan vase ke-b.
Yang kita ingin cari adalah f(0,0).
f(a,b) = 0, jika a==F
f(a,b) = max( f(a+1,c+1) + cost[a][c] ), dimana c dimulai dari b sampai V-(F-a).
F -> banyak bunch
V -> banyak vase
cost[i][j] -> cost bila kita menaruh bunch ke-i pada vase ke-j
Kompleksitas total adalah sekitar O(F^2 * V).

 

15 comments

  1. halo mas timo,…saya akhmad…kebetulan saya pengen banget belajar n menguasai dynamic programming coz kayaknya sering keluar di ACM, so saya minta tolong donk bikin write upnya (source code (C or Java) n langkah-langkahnya dari soal 2262-Bracket) biar paham…thx b4

  2. Halo Akhmad, saya sudah tambahkan file bracket.jpg, kamu bisa download dan rename jadi bracket.cpp. Didalam file tersebut sudah saya berikan dokumentasi. Kalau ada yang kurang jelas bisa kamu tanyakan lagi ke email saya: timotius86@yahoo.com

    – Timo

  3. Termikasih dp nya bagus artikelnya
    cocok untuk pengembangan algoritmanya
    soalnya mungkin bisa lebih kumplit lagi?
    apa saja penerapan dp ?
    ruang lingkupnya samapai sejauh mana untuk dp dan pengembangannya bagaimana?

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s