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

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۴:سوال ۶

سوال ۶

در کارخانه‌ای یک دستگاه وجود دارد که باید n کار را انجام دهد. می‌دانیم که انجام کار iام به اندازه‌ی ti از این دستگاه وقت می‌گیرد و باید حداکثر تا زمان di تحویل داده شود. فرض کنید که دستگاه در زمان صفر شروع به کار می‌کند. علاوه‌بر‌این، می‌دانیم که این دستگاه نمی‌تواند در هر لحظه بیش از یک کار را انجام دهد.

اگر دستگاه در زمان si شروع به انجام کار iام کند، انجام آن در زمان si+ti به پایان خواهد رسید. اگر si+ti>di، یعنی کار iام در زمانی که باید تحویل داده شود هنوز به طور کامل انجام نشده باشد، مقدار Li=si+tidi را دیر کرد کار iام می‌نامیم. در غیر این صورت دیر کرد کار iام برابر با صفر تعریف می‌شود. دیرکرد کل دستگاه برابر با بیش‌ترین دیرکرد کارها، یعنی L=max{L1,L2,,Ln} تعریف می‌شود.

می‌خواهیم ترتیب انجام کارها را به گونه‌ای پیدا کنیم که مقدار دیرکرد کل دستگاه حداقل شود. برای این منظور الگوریتمی به این صورت پیشنهاد داده شده است:

ابتدا کارها را برحسب مقدار di آن‌ها به ترتیب صعودی مرتب می‌کنیم و دستگاه کارها را به‌این‌ ترتیب انجام می‌دهد.

ثابت کنید که این الگوریتم درست عمل می‌کند، یعنی اگر کارها را به این ترتیب انجام دهیم، مقدار دیرکرد کل دستگاه حداقل می‌شود.


ابزار صفحه