حل تشریحی سوال شماره 43 دروس مشترک

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

الف - ورودی: عدد طبیعی n و اعداد حقیقی مثبت $a_n,\dots ,a_1$ و $b_n,\dots ,b_1$

خروجی: یک مجموعه $I\subseteq \left\{1,\dots ,n\right\}$ به طوری‌که ${\sum }_{i\in I}{b}_i$ بیشترین مقدار ممکن را داشته باشد و ${\sum }_{i\in I}{a}_i\le 5$

ب - ورودی: عدد طبیعی و اعداد حقیقی مثبت $a_n,\dots ,a_1$ و $b_n,\dots ,b_1$

خروجی: یک مجموعه $I\subseteq \left\{1,\dots ,n\right\}$ به‌ طوری‌که $\left|I\right|=\left[\frac{n}{2}\right]$ و ${\sum }_{i\in I}{b}_i$ بیشترین مقدار ممکن را داشته

باشد. ( $=\left|I\right|$ تعداد اعضای I)