נגדיר אלגוריתם לבעיית האופטימיזציה Bin-Packing: בהינתן a 1, ,a n, האלגוריתם עובר על המספרים לפי הסדר; אם אפשר…

נגדיר אלגוריתם לבעיית האופטימיזציה $Bin\text{-}Packing$: בהינתן $a_1,\ldots,a_n$, האלגוריתם עובר על המספרים לפי הסדר; אם אפשר הוא מכניס את המספר לתא האחרון שנעשה בו שימוש, ואחרת מכניס אותו לתא חדש.

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