۰
subtitle
ارسال: #۱
مساله زمان بندی با مهلت
اصلن از راه حل این مساله سر درنیاوردم, با اینکه آسونه
۱
ارسال: #۲
RE: مساله زمان بندی با مهلت
سلام.
الگوریتم حریصانه:
کارها رو به ترتیب سود غیرصعودی مرتب کنید و با شروع از بیشترین سود، هر کار رو در دیرترین مهلت ممکن زمانبندی کنید.
لیست کارها به ترتیب سود:
۶۰-۵۵-۴۵-۴۰-۲۰-۱۵-۱۰
اگه مهلت‌ها رو درست خونده باشم:
۱ ۱ ۳ ۲ ۳ ۴ ۲ → مهلت‌ها
به راحتی میشه فهمید که جواب ۱۷۰ خواهد بود. سود کارهای انتخاب شده: ۱۵ + ۴۰ + ۵۵ + ۶۰
ابتدا کار با سود ۶۰ را برای اجرا در نوبت سوم انتخاب می‌کنیم. بعد کار با سود ۵۵ را برای اجرا در نوبت اول انتخاب می‌کنیم. کار با سود ۴۵ قابل زمانبندی نیست، چون تنها در نوبت اول قابل اجراست ولی این نوبت قبلاً اشغال شده. کار با سود ۴۰ را برای اجرا در نوبت دوم انتخاب می‌کنیم. کار با سود ۲۰ قابل زمانبندی نیست، چون تنها در نوبت اول و دوم قابل اجراست، اما این دو نوبت قبلاً اشغال شده‌اند. و ...
الگوریتم حریصانه:
کارها رو به ترتیب سود غیرصعودی مرتب کنید و با شروع از بیشترین سود، هر کار رو در دیرترین مهلت ممکن زمانبندی کنید.
لیست کارها به ترتیب سود:
۶۰-۵۵-۴۵-۴۰-۲۰-۱۵-۱۰
اگه مهلت‌ها رو درست خونده باشم:
۱ ۱ ۳ ۲ ۳ ۴ ۲ → مهلت‌ها
به راحتی میشه فهمید که جواب ۱۷۰ خواهد بود. سود کارهای انتخاب شده: ۱۵ + ۴۰ + ۵۵ + ۶۰
ابتدا کار با سود ۶۰ را برای اجرا در نوبت سوم انتخاب می‌کنیم. بعد کار با سود ۵۵ را برای اجرا در نوبت اول انتخاب می‌کنیم. کار با سود ۴۵ قابل زمانبندی نیست، چون تنها در نوبت اول قابل اجراست ولی این نوبت قبلاً اشغال شده. کار با سود ۴۰ را برای اجرا در نوبت دوم انتخاب می‌کنیم. کار با سود ۲۰ قابل زمانبندی نیست، چون تنها در نوبت اول و دوم قابل اجراست، اما این دو نوبت قبلاً اشغال شده‌اند. و ...
ارسال: #۳
RE: مساله زمان بندی با مهلت
(۲۳ اسفند ۱۳۹۴ ۰۳:۲۵ ب.ظ)MShariati نوشته شده توسط: سلام.ممنون ولی ۱۷۰ تو گزینه ها نیس. جواب ۱۷۵ه. اگه میشه مفصلتر توضیح بدین. مثلن چرا ۴۰ قابل زمانبندی هس ولی ۴۵نه؟؟؟
الگوریتم حریصانه:
کارها رو به ترتیب سود غیرصعودی مرتب کنید و با شروع از بیشترین سود، هر کار رو در دیرترین مهلت ممکن زمانبندی کنید.
لیست کارها به ترتیب سود:
۶۰-۵۵-۴۵-۴۰-۲۰-۱۵-۱۰
اگه مهلت‌ها رو درست خونده باشم:
۱ ۱ ۳ ۲ ۳ ۴ ۲ → مهلت‌ها
به راحتی میشه فهمید که جواب ۱۷۰ خواهد بود. سود کارهای انتخاب شده: ۱۵ + ۴۰ + ۵۵ + ۶۰
ابتدا کار با سود ۶۰ را برای اجرا در نوبت سوم انتخاب می‌کنیم. بعد کار با سود ۵۵ را برای اجرا در نوبت اول انتخاب می‌کنیم. کار با سود ۴۵ قابل زمانبندی نیست، چون تنها در نوبت اول قابل اجراست ولی این نوبت قبلاً اشغال شده. کار با سود ۴۰ را برای اجرا در نوبت دوم انتخاب می‌کنیم. کار با سود ۲۰ قابل زمانبندی نیست، چون تنها در نوبت اول و دوم قابل اجراست، اما این دو نوبت قبلاً اشغال شده‌اند. و ...
۰
ارسال: #۴
RE: مساله زمان بندی با مهلت
۰
ارسال: #۵
RE: مساله زمان بندی با مهلت
توضیح این الگوریتم حریصانه همون یک خطه که گفتم، شما به همون که عمل کنید به جواب درست میرسید.
بقیه‌اش trace الگوریتمه روی این مسئله‌ی خاص، شایدم مهلت‌ها رو درست نخوندم.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
بقیه‌اش trace الگوریتمه روی این مسئله‌ی خاص، شایدم مهلت‌ها رو درست نخوندم.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close