My first Magazine pemrograman-kompetitif-dasar | Page 112

9 Perkenalan Graf
Contoh 3
Contoh Soal 9.3: Kado Iseng
Sebentar lagi Pak Ganesh berulang tahun. Sebagai teman sepermainan, Pak Dengklek
hendak memberikan kado yang berupa tiket konser musisi kesukaannya. Namun, Pak
Dengklek tidak ingin semata-mata memberikan tiket ini. Ia berencana untuk membungkusnya
dalam kotak, yang akan dimasukkan ke dalam kotak lebih besar, dan dimasukkan lagi ke
kotak yang lebih besar, dan seterusnya.
Di gudang, Pak Dengklek memiliki N kotak yang dapat menampung tiket konsernya, dinomori
dari 1 sampai dengan N. Kotak ke-i memiliki ukuran panjang P i , lebar L i , dan tinggi T i . Suatu
kotak a dapat dimuat ke kotak b apabila dipenuhi P a < P b , L a < L b , dan T a < T b . Untuk alasan
estetika, kotak tidak dapat dirotasi.
Pak Dengklek ingin agar hadiahnya dibungkus oleh kotak sebanyak mungkin. Bantulah Pak
Dengklek menentukan banyaknya lapisan kotak terbesar yang mungkin!
Pada soal ini, tidak terdapat graf yang terlihat secara eksplisit. Namun, kita dapat memo-
delkan hubungan antar kotak sebagai graf. Misalkan setiap kotak merepresentasikan sebuah
node . Apabila kotak a dapat dimuat di kotak b, berarti terdapat edge dari a ke b. Struktur graf
ini akan membentuk sebuah directed acyclic graph.
Untuk penyelesaian masalahnya, kita dapat mulai dengan ide yang sederhana: pilih suatu
kotak, masukkan ke salah satu kotak yang lebih besar, dan ulangi secara rekursif untuk kotak
yang lebih besar. Kompleksitas solusi sederhana ini eksponensial terhadap banyaknya kotak,
dan tidak efisien.
Solusi sederhana sebelumnya dapat dibuat lebih baik dengan prinsip dynamic programming .
Definisikan fungsi d p(a) yang menyatakan banyaknya lapisan kotak maksimum yang dapat dicapai
untuk membungkus kotak a. Untuk mencari d p(a), coba semua kemungkinan kotak b yang dapat
membungkus a (atau dengan kata lain, seluruh tetangga dari a). Pilih yang memberikan nilai d p(b)
terbesar, lalu tambahkan dengan 1 karena banyaknya lapisan bertambah. Base case terjadi ketika
tidak ada kotak yang dapat membungkus a, atau himpunan tetangga dari a berupa himpunan
kosong. Untuk kasus tersebut d p(a) = 0.
(
d p(a) =
0,
ad j(a) = {}
1 + max d p(b), ad j(a) 6 = {}
b∈ad j(a)
Jawaban dari soal ini adalah 1 + d p(x), dengan x merupakan salah satu kotak yang membe-
rikan nilai d p terbesar. Kompleksitas dari solusi ini adalah O(E).
102