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

[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 4 adet bilgisayar programınız olsun.
<table><tr><td></td><td>1. program</td><td>2. program</td><td>3. program</td><td>4. program</td></tr><tr><td>p</td><td>5</td><td>5</td><td>10</td><td>4</td></tr><tr><td>w</td><td>8</td><td>6</td><td>20</td><td>7</td></tr></table>
\(\sum_{j=1}^{n} w_j C_j\) toplamını en küçükleyen sıralama aşağıdakilerden hangisidir?

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

Cevap: A 3,4,1,2

Çözüm:
Bu soru şıklardan gidilerek çözülebilir.
3, 4, 1, 2 sıralaması için \(\sum_{j=1}^{n} w_j C_j = 20 \times 10 + 7 \times 14 + 8 \times 19 + 6 \times 24 = 594\).
3, 2, 4, 1 sıralaması için \(\sum_{j=1}^{n} w_j C_j\) = 20 \(\times\) 10 + 6 \(\times\) 15 + 7 \(\times\) 19 + 8 \(\times\) 24 = 615.
3, 4, 2, 1 sıralaması için \(\sum_{j=1}^{n} w_{j} C_{j} = 20 \times 10 + 7 \times 14 + 6 \times 19 + 8 \times 24 = 604\).
2, 4, 1, 3 sıralaması için \(\sum_{j=1}^{n} w_j C_j= 6 \times 5 + 7 \times 9 + 8 \times 14 + 20 \times 24 = 685\).
4, 1, 2, 3 sıralaması için \(\sum_{j=1}^{n} w_{j} c_{j} = 7 \times 4 + 8 \times 9 + 6 \times 14 + 20 \times 24 = 664\).
Doğru cevap \(\sum_{j=1}^{n} w_j C_j\) toplamını 594 yapan 3, 4, 1, 2 sıralamasıdır.