Question

greedy

לרגל הפתיחה המחודשת של קפה קפה בבית הסטודנט הכריזו על מבצע, מי שקונה זוג מוצרים מקבל את הזול ביניהם חינם. בהינתן רשימת קניות המכילה 2n2n מוצרים במחירים p1,,p2np_1, \ldots, p_{2n} נרצה לסדרם בזוגות כך שתתקבל הנחה מקסימלית.

הציעו אלגוריתם המחלק את המוצרים לזוגות, כך שהסכום הכולל שנשלם עבורם יהיה מינימלי. עליכם להוכיח את נכונות האלגוריתם ולנתח את סיבוכיותו.

1

Answers

האלגוריתם: מיין את המוצרים בסדר יורד של המחיר וחלק אותם לזוגות לפי סדר זה.

סיבוכיות: המיון לוקח O(nlogn)O(n\log n).

נכונות: נסמן ב-(ai,bi)(a_i, b_i) את הזוג ה-ii שנבחר לפי האלגוריתם הנ"ל ונוכיח באינדוקציה על ii כי קיים סידור אופטימלי שמכיל את ii הזוגות הראשונים שנבחרו על ידי האלגוריתם הנ"ל:

בסיס: עבור i=0i = 0 הטענה מתקיימת.

צעד: נקבע סידור אופטימלי כלשהו. לפי הנחת האינדוקציה, ii הזוגות הראשונים שייכים לסידור זה, נניח כי הזוג (ai+1,bi+1)(a_{i + 1}, b_{i + 1}) לא שייך לסידור זה ונסתכל על הזוגות (ai+1,c)(a_{i + 1}, c) ו-(bi+1,d)(b_{i + 1}, d) שכן שייכים לסידור זה. נשים לב שההנחה שמתקבלת עבור שני הזוגות הנ"ל היא c+dc + d ואם נחליף את הזוגות ל-(ai+1,bi+1)(a_{i + 1}, b_{i + 1}) ו-(c,d)(c, d) נקבל הנחה של bi+1+min{c,d}c+db_{i + 1} + \min\{c, d\} \geq c + d.

1
Feedback