My first Magazine pemrograman-kompetitif-dasar | Page 87

7.2 Contoh-contoh DP Sederhana
Perhatikan bahwa untuk pemotongan pertama, terdapat N pilihan lokasi pemotongan. Jika
kita memotong di posisi L m , maka didapatkan dua batang, yang mana batang pertama perlu
dipotong di titik L 1 , L 2 , ..., L m−1 dan batang kedua di L m+1 , L m+2 , ..., L N . Dari sini kita mendapatkan
subpersoalan yang serupa. Pemotongan bisa dilanjutkan secara rekursif, dan kita pilih posisi
pemotongan yang ke depannya membutuhkan usaha terkecil.
...
l-1
l
m-1 m
m+1
r r+1
...
Gambar 7.5: Penomoran posisi pemotongan kayu.
Definisikan sebuah fungsi d p(`, r) sebagai jumlah usaha minimum yang mungkin diperoleh,
jika kita hanya perlu memotong di L ` , L `+1 , ..., L r . Untuk kemudahan, asumsikan pula L 0 = 0 dan
L N+1 = M. Untuk menghitung d p(`, r) kita dapat mencoba titik mana yang kita potong pertama
kali. Jika kita memotong di L m (` ≤ m ≤ r), maka kita akan mendapatkan dua potongan.
Dengan demikian, total usaha yang dibutuhkan jika kita melakukan pemotongan di L m adalah
jumlah dari:
• Total usaha minimum dari potongan pertama, yaitu d p(`, m − 1).
• Total usaha minimum dari potongan kedua, yaitu d p(m + 1, r).
• Usaha untuk pemotongan ini, yaitu L r+1 − L `−1 .
Ketika ` > r, artinya sudah tidak ada pemotongan yang perlu dilakukan. Usaha yang dibu-
tuhkan untuk kasus ini adalah 0, atau d p(`, r) = 0.
Dengan demikian, kita dapat merumuskan nilai DP sebagai berikut:
(
d p(`, r) =
0,
`> r
min d p(`, m − 1) + d p(m + 1, r) + (L r+1 − L `−1 ), ` ≤ r
`≤m≤r
Analisis Kompleksitas
Terdapat O(N) nilai berbeda untuk nilai ` dan O(N) nilai berbeda untuk nilai r pada d p(`, r).
Dibutuhkan iterasi sebanyak O(N) untuk menghitung d p(`, r). Sehingga untuk menghitung seluruh
nilai d p(`, r) untuk seluruh ` dan r dibutuhkan waktu O(N 3 ).
Solusi Top-Down
Kita implementasikan d p(`, r) sebagai fungsi SOLVE (`, r).
77