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

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۷:تئوری:سوال ۲۱

سوال ۲۱

دو مسئله‌ی زیر را در نظر بگیرید:

  • مسئله‌ی کوله‌پشتی‎:‎ یک کوله‌پشتی به حجم ‎M‎ داریم‎ (که ‎M‎ می‌تواند خیلی خیلی بزرگ و حتی ناصحیح باشد!). ‎n‎ کیسه به حجم‌های v1‎ تا ‎vn‎ نیز به ما داده شده است. می‌خواهیم بدانیم آیا زیرمجموعه‌ای از کیسه‌ها وجود دارد که مجموع حجم‌های کیسه‌های آن دقیقاً برابر ‎M‎ باشد و کیسه را کاملاً پر کند یا نه؟ دقّت کنید که در یک زیر مجموعه، هر عضو حداکثر یک‌بار می‌آید.
  • مسئله‌ی پازل: یک جدول ‎k‎ سطری و ‎k‎ ستونی از خانه‌های ‎1×1‎ داریم. k2‎ تا شکل نیز به ما داده شده است که هر شکل از تعدادی خانه‌ی ‎1×1‎ به‌هم‌چسبیده تشکیل شده (‎دو خانه به‌هم چسبیده‌اند اگر و فقط اگر در یک پاره‌خط به‌طول ‎1‎ اشتراک داشته باشند؛ از این رو هرشکل،«یک تکّه»‎ است)‎ و مساحت هر شکل حداکثر ‎k2‎ است. می‌خواهیم بدانیم آیا می‌توان تمام جدول را با زیرمجموعه‌ای از این اشکال پوشاند یا نه؟‎ پوشش جدول به معنی قرار دادن تعدادی از اشکال موجود روی خانه‌های جدول است که هر خانه‌ی جدول دقیقاً و به‌طور کامل زیر یکی از اشکال باشد. دقّت کنید که از هر شکل حداکثر یک‌بار می‌توانیم استفاده کنیم و در این یک بار می‌توانیم شکل را بچرخانیم یا حتی دوران بدهیم. برای مثال شکل روبه‌رو را به ‎8‎ طریق می‌توان در جدول قرار داد.

فرض کنید یک ماشین جادویی اختراع شده که مسئله‌ی کوله‌پشتی را در زمان چندجمله‌ای برحسب ‎n‎ حل می‎‌کند (‎روایتی از این مسئله که به‌صورت داینامیک حل می‌شود چند جمله‌ای بر حسب ‎M‎ و ‎n‎ است؛ نه فقط بر حسب ‎n‎). ثابت کنید می‌توان با استفاده از این ماشین، مسئله‌ی پازل را نیز در زمان چند جمله‌ای برحسب ‎k حل کرد.


ابزار صفحه