My first Magazine pemrograman-kompetitif-dasar | Page 78

7 Dynamic Programming
f (12) = min( f (12 − 1) + 1, f (12 − 6) + 1, f (12 − 10) + 1)
= min( f (11) + 1, f (6) + 1, f (2) + 1)
= min(2 + 1, 1 + 1, 2 + 1)
= min(3, 2, 3)
= 2
Maka, tabel akhirnya dapat dilihat pada Tabel 7.6.
x
f (x)
0
0
Tabel 7.6: Tahap 6: Isi akhir tabel.
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 1 2 3 4 1
11
2
12
2
Analisis Bottom-Up
Bottom-up tidak mengalami perlambatan dari overhead pemanggilan fungsi. Bottom-
up juga memungkinkan penggunaan teknik DP lanjutan seperti flying table, kombinasi dengan
struktur data tree, atau teknik-teknik lanjutan lainnya. Namun, Anda harus memikirkan urutan
pengisian nilai tabel. Selain itu, semua tabel harus diisi nilainya walaupun tidak dibutuhkan
akhirnya.
II Sekilas Info JJ
Karena sifatnya yang memanfaatkan subpersoalan, soal yang dapat diselesaikan secara
greedy biasanya dapat juga diselesaikan secara DP, meski biasanya lebih lambat dari segi
kompleksitas waktu. Jika Anda tidak dapat memformulasikan solusi greedy , cobalah sele-
saikan secara DP! Selain itu, kebenaran solusi DP lebih mudah untuk dibuktikan. Sehingga
solusi DP dapat digunakan untuk menguji kebenaran solusi greedy Anda.
7.2
Contoh-contoh DP Sederhana
Untuk membiasakan diri berpikir secara DP, kita akan selesaikan beberapa contoh persoalan
DP sederhana.
7.2.1 Knapsack
Contoh Soal 7.2: Knapsack
Diberikan N buah barang, dinomori dari 1 sampai N. Barang ke-i memiliki harga v i rupiah
dan berat w i gram. Kita memiliki tas yang berkapasitas G gram. Kita ingin memasukkan
beberapa barang ke dalam tas, sedemikian sehingga jumlah berat dari barang-barang yang
kita masukan tidak lebih dari kapasitas tas dan jumlah harganya sebanyak mungkin.
Contoh
68