سوال ۱۳

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

1. $a \prec a$
2. $a\prec b\quad \&\quad b \prec a \Rightarrow a=b$
3. $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$ ثابت است)، یک الگوریتم چند جمله‌ای برای حل این مسئله ارائه دهید.

• سوال بعد
• سوال قبل