Input text yang akan diprint adalah sejumlah n words/kata-kata dengan panjang setiap kata adalah l1,l2…, ln karakter. Paragraph yang yang terdiri dari words akan diprint dengan rapi dalam sejumlah baris dengan memuat M karakter maksimum setiap baris.
Kriteria hasil print yang rapi adalah: Jika sebuah baris terdiri dari words I sampai j dimana I <= j dan terdapat sebuah space/spasi antar words, jumlah extra space karakter pada akhir baris adalah
Step 1. Struktur pembentukan print yang rapi.
Kita asumsikan bahwa kita mengetahui baris terakhir mulai dari kata i sampai kata j. Sehingga baris sebelumnya akan memuat kata 1,…,i-1.
Misalkan c[j] adalah cost dari susunan optimal dari kata 1,…,j. Jika kita mengetahui baris terakhir memuat kata I,…,j maka Jika kita menghitung c[1], maka kita membutuhkan c[0]. Jika c[0] = 0 maka c[1]=lc[1,1].
Untuk mendapatkan kata mana yang akan dibentuk pada sebuah line, kita dapat membuat parallel p yang menunjukkan masing-masing asal/sumber nilai cost(c). Ketika c[j] dihitung, jika c[j] sesuai dengan nilai c[k-1], set p[j] = k. Selanjutnya setelah c[n] dihitung, kita dapat menemukan pointer dimana untuk break/pemutusan baris. Baris akhir dimulai dari kata[n] sampai kata n. Baris sebelumnya dimulai dari p[p[n]] sampai kata p[n]-1, demikian selanjutnya
Step 2. Solusi Rekursif.
Kita perlu mengetahui kata mana yang memulai baris akhir untuk subproblem dari kata 1,…,j. Oleh karena itu kita mencoba semua kemungkinan untuk kata i, dan kita pilih satu yang memberikan cost paling rendah. Disini i disusun dari 1 sampai j. Jadi, kita dapat mendefinisikan c[j] secara rekursif dari:
Ketentuan untuk lc
• Semua pilihan yang dibuat akan dapat disusun dalam line(karena susunan dengan tidak dapa dipilih sebagai minimum)
• Cost dalam menempatkan kata i,…,j pada baris terakhir tidak akan 0 kecuali jika baris terakhir pada paragraph (j = n) atau kata i…j akan diisi oleh baris yang sudah ada.
Kita dapat menghitung nilai c dari kiri kekanan karena setiap nilai tergantung pada nilai sebelumnya.
15-6 Checkboard Problem
Terdapat sebuah papan yang berukuran n x n dan sebuah bidak diletakkan pada pojok bawah pada papan. Tujuan dari permainan ini adalah bagaimana memindahkan bidak dari ujung papan bawah ke ujung papan atas dan tiap perpindahan bidak pemain akan mendapatkan uang. Pemain diharapkan akan memperoleh uang sebanyak-banyaknya dari perpindahan bidak.
Aturan berpindah:
1. bidak hanya dapat berpindah satu kotak diatasnya.
2. Bidak dapat berpindah satu kotak keatas dan satu kotak ke kiri.
3. Bidak dapat berpindah satu kotak keatas dan satu kotak ke kanan.
Step 1. Struktur perjalanan bidak.
Dimisalkan baris papan dilambangkan dengan A dan kolom dilambangkan dengan B . pada akhir perjalanan, bidak akan menempati kotak (A,B) dan sebelum tiba pada kotak (A,B), bidak akan melewati kotak (A’,B-1) dengan A’ = A-1 atau A atau A+1. Jika perjalanan dari (A’,B-1) menuju (A,B) kita mendapatkan uang sebanyak p ((A’,B-1), (A,B)) dollar dan perjalan dari titik (A’,B-1) dati titik sebelumnya sebanyak d dollar, maka jumlah uang yang dikumpulkan dari perjalanan titik awal sampai perjalanan titik akhir sebanyak d+ p ((A’,B-1), (A,B)) dollar
Step 2. Solusi Rekursif.
Untuk mendapatkan uang terbanyak untuk sampai ke (A,B) maka harus dicari juga jalan yang paling menguntungkan untuk sampai ke (A+1, B-1), (A+1, B), dan (A +1, B +1) .
Dari persamaan untuk mendapatkan nilai uang terbesar ke titik akhir pada step 1, dapat dicari bahwa untuk mendapatkan nilai uang terbanyak untuk sampai ke titik (A,B) atau d(A,B) adalah dengan melewati ketiga jalur di bawah ini :
Artikel ini seharusnya mengandung beberapa gambar yang menerangkan persoalan dan rumus-rumus yang berbentuk gambar. untuk lebih lengkapnya silahkan mengirimkan email permintaan file lengkap dalam bentuk microsoft word document ke penulis
Tidak ada komentar:
Posting Komentar