נגדיר אלגוריתם קירוב בשם Next-Fit לבעיית האופטימיזציה של Bin-Packing: קלט: a 1, ,a n , כאשר a 1, ,a n (0,1] ו-…

נגדיר אלגוריתם קירוב בשם $Next\text{-}Fit$ לבעיית האופטימיזציה של $Bin\text{-}Packing$:

קלט: $\langle a_1,\ldots,a_n\rangle$, כאשר $a_1,\ldots,a_n\in(0,1]$ ו-$n\in\mathbb N$.
לכל $i=1,\ldots,n$:

1. אם $a_i$ יכול להיכנס לתא האחרון שפתחנו, הכנס אותו.

2. אחרת, פתח תא חדש והכנס אליו את $a_i$.

3. הוכיחו כי זמן הריצה של האלגוריתם פולינומי.

4. הוכיחו כי בכל חלוקה לתאים שמחזיר האלגוריתם, סכום האיברים שהוכנסו לשני תאים סמוכים גדול מ-$1$.

5. הוכיחו כי האלגוריתם משיג יחס קירוב $2$.