سوال ۷۹ کنکور ارشد علوم کامپیوتر ۱۴۰۲

فرض کنیم $P \ne NP$. کدام مسئله یا مسائل زیر دارای الگوریتم چندجمله‌ای است؟

الف) ورودی: عدد طبیعی $n$ و اعداد حقیقی مثبت $a_1, \cdots, a_n$ و $b_1, \cdots, b_n$. خروجی: یک مجموعهٔ $I \subseteq \{1, \cdots, n\}$ به‌طوری که $\sum_{i \in I} b_i$ بیشترین مقدار ممکن را داشته و $\sum_{i \in I} a_i \le ۵$.

ب) ورودی: عدد طبیعی $n$ و اعداد حقیقی مثبت $a_1, \cdots, a_n$ و $b_1, \cdots, b_n$. خروجی: یک مجموعهٔ $I \subseteq \{1, \cdots, n\}$ به‌طوری که $|I| = \left\lceil \frac{n}{۲} \right\rceil$ و $\sum_{i \in I} b_i$ بیشترین مقدار ممکن را داشته باشد. ($|I| =$ تعداد اعضای $I$)