Bilgisayar Olimpiyatı 2024, 1. Aşama, Soru 28

[27-29 soruları için açıklama]
Elinizde tek çekirdekli bir bilgisayar ve bu bilgisayar üzerinde çalıştırmanız gereken n adet bilgisayar programı vardır. Bilgisayar programları 1'den n'ye kadar numaralandırılmış olsunlar. Girdi olarak size her bir bilgisayar programı için 2 pozitif sayı verilmektedir.
- \(p_j > 0\) sayısı j. bilgisayar programının çalışma süresini,
- \(w_j > 0\) sayısı ise j. bilgisayar programının önemini göstermektedir.
Bilgisayar \(t = 0\) anında kullanımınıza hazırdır. Bilgisayar aynı anda en fazla bir programı çalıştırabilmektedir. Sizin göreviniz hangi bilgisayar programının hangi zaman aralığında çalışacağını belirlemektir.
Oluşturduğunuz zaman çizelgesine göre j. bilgisayar programının çalışmasının sonlandığı zaman \(C_j\) olsun.
Amacınız zaman çizelgesini \(\sum_{j=1}^{n} w_j C_j\) değerini en küçükleyecek şekilde oluşturmaktır.
\(n\)
\(\sum_{j=1}^{n} w_j C_j\) değerini en küÇüklemek istediğiniz için çalıştıracağınız ilk bilgisayar programını \(t = 0\) anında başlatmanız gerektiğine ve her bir bilgisayar programını çalıştırmaya bir önceki bilgisayar programının çalışması biter bitmez başlamanız gerektiğine dikkat ediniz.
Örnek: \(p\) ve \(w\) değerleri aşağıdaki tabloda verilen şekilde olan 3 adet bilgisayar programınız olsun.
<table><tr><td></td><td>1. program</td><td>2. program</td><td>3. program</td></tr><tr><td>\(p\)</td><td>3</td><td>4</td><td>2</td></tr><tr><td>\(w\)</td><td>6</td><td>1</td><td>2</td></tr></table>
Bu örnekte verilen programları 3! = 6 farklı şekilde sıralamak mümkündür.
Programlar 1, 2, 3 şeklinde sıralanırlarsa çalışmalarının sonlanma süreleri \(C_1 = 3\), \(C_2 = 7\), \(C_3 = 9\) olur.
Bu sıralamaya göre \(\sum_{j=1}^{n} w_j C_j = 6 \times 3 + 1 \times 7 + 2 \times 9 = 43\) olur.
Programlar 1, 3, 2 şeklinde sıralanırlarsa çalışmalarının sonlanma süreleri \(C_1 = 3\), \(C_2 = 9\), \(C_3 = 5\) olur. Bu sıralamaya göre \(\sum_{j=1}^{n} w_j C_{j} = 6 \times 3 + 1 \times 9 + 2 \times 5 = 37\) olur. Bu sıralama \(\sum_{j=1}^{n} w_j C_j\) değerini en küçükleyen sıralamadır.

---

p ve w değerleri aşağıdaki tabloda verilen şekilde olan 8 adet bilgisayar programınız olsun.
<table><tr><td></td><td>1. program m</td><td>2. program m</td><td>3. program m</td><td>4. program m</td><td>5. program m</td><td>6. program m</td><td>7. program m</td><td>8. program m</td></tr><tr><td>p</td><td>1</td><td>2</td><td>1</td><td>2</td><td>4</td><td>2</td><td>3</td><td>4</td></tr><tr><td>w</td><td>2</td><td>3</td><td>3</td><td>4</td><td>6</td><td>6</td><td>6</td><td>6</td></tr></table>
Aşağıdaki
sıralamalardan hangisi \(\sum_{j=1}^{n} w_j C_j\) toplamını en küçükleyen sıralamalardan biridir?

Şıklar:
A) 8,4,5,1,7,2,3,6 | B) 1,4,7,2,5,8,6,3 | C) 5,6,7,8,4,2,3,1 | D) 1,3,2,4,6,7,5,8 | E) 3,6,1,4,7,2,8,5

Cevap: E 3,6,1,4,7,2,8,5

Çözüm:
Bu soru bilgisayar programlarını \(\frac{w_j}{p_j}\) değerlerine göre büyükten küçüğe sıralayarak çözülebilir.
\[
\frac{w_3}{p_3} = \frac{w_6}{p_6} = 3 \text{ olduğu için } 3 \text{ ve } 6 \text{ numaralı programlardan ilk başta olmalıdır.}
\]
\[
\frac{w_1}{p_1} = \frac{w_4}{p_4} = \frac{w_7}{p_7} = 2 \text{ olduğu için } 1, 4 \text{ ve } 7 \text{ numaralı programlardan daha sonra gelmelidir.}
\]
\[
\frac{w_2}{p_2} = \frac{w_5}{p_5} = \frac{w_8}{p_8} = 1.5 \text{ olduğu için } 2, 5 \text{ ve } 8 \text{ numaralı programlar herhangi bir sırayla en sonda gelmelidir.}
\]
Şıklardan sadece 3, 6, 1, 4, 7, 2, 8, 5 bu şartları sağlamaktadır.