Pembahasan Soal bebek

Soal ini sepintas nampaknya rumit sekali tetapi dengan menganalisanya terlebih dahulu maka anda akan menemukan soal yang jauh lebih sederhana.

Pertama kita bahas dahulu submasalah pengurutan bebek satu varietas, i.e."jika ada n bilangan acak yang masing-masing unik, berapa banyak pemindahan minimum yang perlu dilakukan untuk mengurutkannya".

Ide dari pemecahan masalah ini adalah: mencari berapa banyak di antara bilangan-bilangan itu yang sudah dalam pengurutan. Ada sejumlah cara pengurutan, oleh pada setiap bilangan kita hitung suatu indeks keterurutan (IK) yang didefinisikan sbb.

IK suatu bilangan adalah adalah jumlah bilangan disebelah kirinya yang lebih kecil darinya namun berada dalam keterurutan termasuk bilangan itu sendiri.

Perhatikan bilangan-bilangan ini: 1, 3, 2, 7, 4, 6, 5

Indeks-indeks keterurutan diperoleh sbb (dituliskan di dalam tanda kurung),
1(1), 3(2), 2(2), 7(3), 4(3), 6(4), 5(4)

Berapa banyak bilangan yang tidak dalam keterurutan adalah banyaknya bilangan dikurangi oleh IK maksimum. Untuk contoh tersebut maka IK maksimum adalah 4 dan ada 7 bilangan sehingga jumlah pemindahan (yang dilakukan pada bilangan yang tidak berada dalam urutan tersebut) adalah 7 -4 = 3.

Sekarang jika kita lakukan pada bilangan-bilangan ini: 1, 2, 3, 4, 5, 6, 7 Maka diperoleh
1(1), 2(2), 3(3), 4(4), 5(5), 6(6), 7(7) dan jumlah pemindahan adalah = 7 - 7 = 0.

Kita coba lagi pada bilangan-bilangan ini: 7, 6, 5, 4, 3, 2, 1 Maka diperoleh 7(1), 6(1), 5(1), 4(1), 3(1), 2(1), 1(1)
dan jumlah pemindahan adalah = 7 - 1 = 6.

Beruntunglah soal ini tidak meminta cara-cara pemindahannya karena untuk contoh di atas akan terdapat banyak kemungkinan yang dapat dilakukan untuk 3 kali pemindahan tesebut. Itu terlihat dari adanya indeks yang sama seperti bilangan 3 dan 2, bisa 2 maupun 3 yang dipindahkan.

Ok, jadi bagaimana algoritmanya? Saat menghitung IK untuk X[j] kita cukupmenemukan bilangan yang lebih kecil darinya dengan IK terbesar, misalnya X[k], dan menghitung IK[j] := IK[k] + 1

for j := 1 to N do begin
    IKtmp := 0;
    for k := 1 to j-1 do
        if (X[k] < X[j] and IK[k] > IKtmp) then
            IKtmp := IK[k];
    IK[j] = IKtmp + 1;
end;

Sekarang bagaimana dengan varietas lebih dari satu? Gampang, karena soal membatasi jumlah varietas hanya 4 maka pertama kita permutasikan urutan varietas, lalu memberi tambahan bobot sesuai dengan urutan varietasnya. Misalnya untuk urutan varietas v1, v2, v3, v4 maka bobot setiap bebek dari v2 di tambah 100, dari v3 di tambah 200, di v4 di tambah 300 (mengapa kelipatan 100? Karena bobot maksimum bebek 100!). Kemudian untuk satu permutasi dilakukan penghitungan IK sepertinya hanya satu varietas saja.

Untuk jumlahvarietas = 4 maka terdapat 24 permutasi, berati pula ada 24 kali penghitungan IK dan masing-masing diperoleh jumlah pemindahan yang perlu dilakukan. Dari ke 24 jumlah pemindahan untuk masing-masing permutasi diambil jumlah yang paling minimum.

Lalu, bagaimanakah melakukan permutasi? Silahkan membaca lagi bahan PJJ yang lalu....