באלגוריתם First Fit לאריזה בהרצאה שראינו מתאים בהריזה על איברי הקלט, עוברים לפי הסדר ומכניסים את a 1, ..., a n…

באלגוריתם First Fit לאריזה בהרצאה שראינו מתאים בהריזה על איברי הקלט, עוברים לפי הסדר ומכניסים את $a_1, ..., a_n$ את $aj (1\le i\le n)$ לתא הראשון שקיים לו סכום איברי התא בתוספת aj הוא לכל היותר 1 (ואם אין תא כזה פותחים תא חדש ומכניסים את aj אליו). נשנה את האלגוריתם כך שנכניס את $aj (1\le i\le n)$ לתא שבו קיים אם לתא סכום איברי התא בתוספת aj הוא 6/7 לכל היותר. בהרצאה ראינו יחס קירוב של 2 לאלגוריתם המקורי. אם ננתח את יחס הקירוב של האלגוריתם החדש באופן דומה, מה הטענה החזקה ביותר הנכונה מבין הטענות הבאות שנקבל? הערות: (I שימו לב שהגדרת הבעיה היא להשתנה - כל תא יכול להכיל איברים שסכומם עד 1. לכן (בניגוד לאלגוריתם שהגדרנו לעיל), לאלגוריתם אופטימלי מותר להכניס לתא איברים שסכומם עד 1. (II הניחו שהפתרון האופטימלי מתחלק בכל המספרים 2, 3, ... , 10.