My first Magazine pemrograman-kompetitif-dasar | Page 86

7 Dynamic Programming
7.2.4
Memotong Kayu
Contoh Soal 7.5: Memotong kayu (Diadopsi dari UVa 10003 - Cutting Sticks 11 )
Kita akan memotong sebuah batang kayu dengan panjang M meter pada N titik menjadi
N + 1 bagian. Titik ke-i berada di L i meter dari ujung kiri, dengan 1 ≤ i ≤ N. Untuk memotong
sebatang kayu menjadi dua, kita memerlukan usaha sebesar panjang kayu yang sedang
kita potong. Cari urutan pemotongan sedemikian sehingga total usaha yang dibutuhkan
minimum!
Contoh
Contoh, terdapat sebuah kayu dengan panjang 10 meter dan terdapat 3 titik potongan
pada 2 meter, 4 meter, dan 7 meter dari ujung kiri.
4
2
7
Gambar 7.2: Ilustrasi pemotongan kayu.
Kita bisa memotong pada titik 2, titik 4, lalu titik 7 dan memerlukan usaha 10 + 8 + 6 =
24.
2
4
7
+10
+8
+6
Gambar 7.3: Langkah pemotongan kayu.
Cara lain adalah memotong pada titik 4, titik 2, lalu titik 7 dan memerlukan usaha 10 + 4 +
6 = 20.
2
4
7
+10
+4
+6
Gambar 7.4: Langkah pemotongan kayu yang lebih optimal.
76