====== سوال ۱۳ ======


$n$ نوع جنس مختلف وجود دارند که جنس $i$ به اندازه‌ی $s(i)$ حجم اشغال می‌کند و به اندازه‌ی $v(i)$ ارزش دارد. علاوه بر این یک رابطه‌ی ترتیب جزئی روی این جنس‌ها تعریف شده است. این رابطه را با $\prec$ نشان می‌دهیم. رابطه ترتیب جزئی به این معناست که:

  - $a \prec a$
  - $a\prec b\quad \&\quad b \prec a \Rightarrow a=b$
  - $a\prec b\quad \&\quad b \prec c \Rightarrow a \prec c$


یک کوله‌پشتی با ظرفیت $B$‌داریم و می‌خواهیم تعدادی از این اجناس را طوری انتخاب کنیم که:

  * مجموع حجم آن‌ها از ظرفیت کوله‌پشتی تجاوز نکند.
  * هرگاه جنس $u$ را انتخاب کرده باشیم و $u'\prec u$ در این‌صورت باید $ u'$ را نیز انتخاب کنیم.
  * مجموع ارزش اجناس انتخاب شده ماکزیمم باشد.

اگر رابطه‌ی ترتیب بین اجناس به‌صورت درخت ریشه‌دار باشد و $s(u)\leq C;u: 1…n$ ( $C$ ثابت است)، یک الگوریتم چند جمله‌ای برای حل این مسئله ارائه دهید.


   * [[سوال ۱۴|سوال بعد]]
   * [[سوال ۱۲|سوال قبل]]