permasalahanya!!!
Sebuah stduio musik membuka layanan penyewaan studio. Studio ini hanya beroperasi dari jam 1-14, setiap group band yang akan menyewa di wajibkan membocking 2 hari sebelumnya. Pemilik studio wajib memilih grup band mana saja yang di perbolekan menyewa. satu slot hanya boleh digunakan satu grup band pada hari itu, misakan 2 hari lalu terdapat 10 grup band yang sudah memesanan :
Persoalan :
1.selesaikan dengan algoritma brute force. Tentukan grup band mana saja yang di perbolehkan latihan!!!
2.selesaikan dengan algoritma greedy. Jelaskan srategi greedy yang mungkin dapat diterapkan agar diperoleh grup band yan paling banyak pada hari ini!!!
menggunakan algoritma brute force.
okey,,,srateginya :
1. urutkan terlebih dahulu grup band dari yang terkecil ke terbesar berdasarkan jam mulai.
jadi seperti ini :
2. grup band urutan ke satu yang terpilih pertama.
3. kemudian pilih aktivitas yang waktu mulainya lebih besar atau sama dengan
waktu selesai aktivitas yang dipilih sebelumnya .
ini algoritmanya :
kita coba !!!
i = 2 // berarti yang no ke 2 yaitu grup band C
2 >= 3 // (2 adalah jam awal dari C dan 3 adalah jam akhir dari A ) tidak maka lanjut ke i = 3
i = 3 // no ke 3 yaitu grup band B
3 >= 3 // (3 adalah jam awal dari B dan 3 adalah jam akhir dari A )cocok maka
g ← g U { i } // i disini adalah B, jadi B gabungkan ke dalam g
j ← i // j adalah jam akhir jadi jam akhir yang di pakai adalah jam akhir grup B yaitu 4
i = 4 // no ke 4 yaitu grup band D
5 >= 4 // (5 adalah jam awal dari D dan 4 adalah jam akhir dari B ) cocok maka
g ← g U { i } // i disini adalah D, jadi D gabungkan ke dalam g
j ← i // j adalah jam akhir, jadi jam akhir yang di pakai adalah jam akhir grup D yaitu 7
i = 5 // no ke 5 yaitu grup band F
7 >= 7 // 7 adalah jam awal dari F dan 7 adalah jam akhir dari D ) cocok maka
g ← g U { i } // i disini adalah F, jadi F gabungkan ke dalam g
j ← i // j adalah jam akhir, jadi jam akhir yang di pakai adalah jam akhir grup F yaitu 10
i = 6 // berarti yang no ke 6 yaitu grup band E
8 >= 10 //(8 adalah jam awal dari E dan 10 adalah jam akhir dari F )tidak maka lanjut ke i = 7
i = 7 // berarti yang no ke 7 yaitu grup band G
9 >= 10 //(9 adalah jam awal dari G dan 10 adalah jam akhir dari F )tidak maka lanjut ke i = 8
i = 8 // berarti yang no ke 8 yaitu grup band I
9 >= 10 //(9 adalah jam awal dari I dan 10 adalah jam akhir dari F )tidak maka lanjut ke i = 9
i = 9 // no ke 5 yaitu grup band H
11 >= 10 // (11 adalah jam awal dari H dan 7 adalah jam akhir dari F ) cocok maka
g ← g U { i } // i disini adalah H, jadi H gabungkan ke dalam g
j ← i // j adalah jam akhir, jadi jam akhir yang di pakai adalah jam akhir grup H yaitu 12
i = 10 // no ke 10 yaitu grup band J
12 >= 12 // (12 adalah jam awal dari J dan 12 adalah jam akhir dari H ) cocok maka
g ← g U { i } // i disini adalah J, jadi J gabungkan ke dalam g
j ← i // j adalah jam akhir, jadi jam akhir yang di pakai adalah jam akhir grup J yaitu 14
i = 11 //keluar dari perulangan
jadi grup band yang bisa memakai studio pada har i ini yaitu g = {A, B, D, F, H, J }
2. menggunakan algoritma greedy
pilih aktivitas yang durasinya paling kecil lebih dahulu dan waktu mulainya tidak lebih besar dari waktu selesai aktivitas lain yang telah terpilih.
Kemudian lakukan perulangan seperti srategi yang pertama dan waktu mulainya tidak lebih besar dari waktu selesai aktivitas lain yang telah terpilih dari langkah di atas.
Maka grup band yang terpilih yaitu g = {A, B, D, E, G, H, J}
i = 2 // berarti yang no ke 2 yaitu grup band C
2 >= 3 // (2 adalah jam awal dari C dan 3 adalah jam akhir dari A ) tidak maka lanjut ke i = 3
i = 3 // no ke 3 yaitu grup band B
3 >= 3 // (3 adalah jam awal dari B dan 3 adalah jam akhir dari A )cocok maka
g ← g U { i } // i disini adalah B, jadi B gabungkan ke dalam g
j ← i // j adalah jam akhir jadi jam akhir yang di pakai adalah jam akhir grup B yaitu 4
i = 4 // no ke 4 yaitu grup band D
5 >= 4 // (5 adalah jam awal dari D dan 4 adalah jam akhir dari B ) cocok maka
g ← g U { i } // i disini adalah D, jadi D gabungkan ke dalam g
j ← i // j adalah jam akhir, jadi jam akhir yang di pakai adalah jam akhir grup D yaitu 7
i = 5 // no ke 5 yaitu grup band F
7 >= 7 // 7 adalah jam awal dari F dan 7 adalah jam akhir dari D ) cocok maka
g ← g U { i } // i disini adalah F, jadi F gabungkan ke dalam g
j ← i // j adalah jam akhir, jadi jam akhir yang di pakai adalah jam akhir grup F yaitu 10
i = 6 // berarti yang no ke 6 yaitu grup band E
8 >= 10 //(8 adalah jam awal dari E dan 10 adalah jam akhir dari F )tidak maka lanjut ke i = 7
i = 7 // berarti yang no ke 7 yaitu grup band G
9 >= 10 //(9 adalah jam awal dari G dan 10 adalah jam akhir dari F )tidak maka lanjut ke i = 8
i = 8 // berarti yang no ke 8 yaitu grup band I
9 >= 10 //(9 adalah jam awal dari I dan 10 adalah jam akhir dari F )tidak maka lanjut ke i = 9
i = 9 // no ke 5 yaitu grup band H
11 >= 10 // (11 adalah jam awal dari H dan 7 adalah jam akhir dari F ) cocok maka
g ← g U { i } // i disini adalah H, jadi H gabungkan ke dalam g
j ← i // j adalah jam akhir, jadi jam akhir yang di pakai adalah jam akhir grup H yaitu 12
i = 10 // no ke 10 yaitu grup band J
12 >= 12 // (12 adalah jam awal dari J dan 12 adalah jam akhir dari H ) cocok maka
g ← g U { i } // i disini adalah J, jadi J gabungkan ke dalam g
j ← i // j adalah jam akhir, jadi jam akhir yang di pakai adalah jam akhir grup J yaitu 14
i = 11 //keluar dari perulangan
jadi grup band yang bisa memakai studio pada har i ini yaitu g = {A, B, D, F, H, J }
2. menggunakan algoritma greedy
pilih aktivitas yang durasinya paling kecil lebih dahulu dan waktu mulainya tidak lebih besar dari waktu selesai aktivitas lain yang telah terpilih.
Kemudian lakukan perulangan seperti srategi yang pertama dan waktu mulainya tidak lebih besar dari waktu selesai aktivitas lain yang telah terpilih dari langkah di atas.
Maka grup band yang terpilih yaitu g = {A, B, D, E, G, H, J}
1 Comment
