נזכיר את בעיית האריזה בתאים. קלט: n-ייה של מספרים a 1, ,a n (0,1] ומספר טבעי k . שאלה: האם קיימת חלוקה של a 1,…

נזכיר את בעיית האריזה בתאים.

קלט: $n$-ייה של מספרים $a_1,\ldots,a_n\in(0,1]$ ומספר טבעי $k\in\mathbb{N}$.

שאלה: האם קיימת חלוקה של $a_1,a_2,\ldots,a_n$ ל-$k$ תאים כך שסכום המספרים בכל תא לכל היותר 1.

א. הוכיחו כי בעיית האריזה בתאים היא $NP$ קשה. ב. נסחו את בעיית האופטימיזציה המתאימה לבעיית האריזה בתאים, והוכיחו כי אם קיים אלגוריתם קירוב פולינומי לבעיית האריזה בתאים עם יחס קירוב 1.49 אז $P=NP$.