Q9 DAA

Terdapat 9 rumah dalam sebuah kompleks. 

Akan dipasang instalasi air pada rumah-rumah tersebut dengan menggunakan 6 buah pipa. 

Sebuah pipa memiliki dua ujung : ujung MASUK dan ujung KELUAR

Sebuah rumah hanya boleh memiliki satu ujung pipa KELUAR dan satu ujung pipa MASUK.

Rumah yang hanya memiliki ujung pipa KELUAR akan dipasangi TANGKI AIR.

Rumah yang hanya memiliki ujung pipa MASUK akan dipasangi KERAN.

Berikut adalah deretan-deretan angka yang melambangkan RUMAH ASAL, RUMAH TUJUAN, dan PANJANG PIPA antar rumah:

7, 4, 98

5, 9, 72

4, 6, 10

2, 8, 22

9, 7, 17

3, 1, 66

Berdasarkan data tersebut, ada berapa jumlah TANGKI AIR dan KERAN?

• 2

• 3

• 4

• 5

Berdasarkan Soal 9.1, tentukan panjang pipa TERKECIL untuk masing-masing saluran.

• 22, 66, 27

• 10, 17, 22

• 22, 66, 10

• 10, 17, 66

Pilihlah subset terbaik dimana total berat nya tidak melebihi 11 kg dan total value nya semaksimal mungkin. Semua item hanya dapat diambil 1x saja.

Sebuah algoritma greedy mengurutkan item-item tersebut berdasarkan value item dibagi berat item (vi/wi) secara descending dan akan dijadikan sebagai subset mulai dari item pertama yang ada pada daftar item yang sudah di sortir.

V_Optimal = Total value dari subset yang didapatkan menggunakan algoritma yang optimal.

V_Greedy = Total value dari subset yang didapatkan menggunakan algoritma greedy.

Hasil dari V_Optimal - V_Greedy adalah ____

• 38

• 20

• 16

• 4

Diberikan sebuah permasalahan penyusunan jadwal pekerjaan yang dimana kita dituntut untuk dapat memberikan hasil dengan jumlah pekerjaan yang dilakukan sebanyak mungkin dimana tidak ada pekerjaan yang overlap

Contoh kasus dan solusinya:

[x, y] → x = waktu mulai, y = waktu berakhir.

Input:

List = [1, 3], [2, 4], [3, 5], [4, 6], [5, 7]

Output:

Jumlah pekerjaan = 3

Pekerjaan yang dilakukan = [1, 3], [3, 5], [5, 7]

Diberikan List sebagai berikut:

[1, 6], [1, 3], [5, 8], [8, 11], [7, 9], [2, 3], [4, 7]

Apabila greedy score yang digunakan adalah:

Pekerjaan yang selesai duluan (e_j terkecil) diprioritaskan.

Berapa jumlah pekerjaan yang mungkin didapatkan dari list tersebut?

• 2

• 3

• 4

• 6