Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۸:الگوریتم ها:سوال ۱۳

سوال ۱۳

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

  1. aa
  2. ab&baa=b
  3. ab&bcac

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

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

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


ابزار صفحه