اصلن از راه حل این مساله سر درنیاوردم, با اینکه آسونه
(۲۲ اسفند ۱۳۹۴ ۰۹:۳۳ ب.ظ)dokhtare payiz نوشته شده توسط: اصلن از راه حل این مساله سر درنیاوردم, با اینکه آسونه
عکستون خیلی کم کیفیته اصلا اعدادش واضح نیست
سلام.
الگوریتم حریصانه:
کارها رو به ترتیب سود غیرصعودی مرتب کنید و با شروع از بیشترین سود، هر کار رو در دیرترین مهلت ممکن زمانبندی کنید.
لیست کارها به ترتیب سود:
۶۰-۵۵-۴۵-۴۰-۲۰-۱۵-۱۰
اگه مهلتها رو درست خونده باشم:
۱ ۱ ۳ ۲ ۳ ۴ ۲ → مهلتها
به راحتی میشه فهمید که جواب ۱۷۰ خواهد بود. سود کارهای انتخاب شده: ۱۵ + ۴۰ + ۵۵ + ۶۰
ابتدا کار با سود ۶۰ را برای اجرا در نوبت سوم انتخاب میکنیم. بعد کار با سود ۵۵ را برای اجرا در نوبت اول انتخاب میکنیم. کار با سود ۴۵ قابل زمانبندی نیست، چون تنها در نوبت اول قابل اجراست ولی این نوبت قبلاً اشغال شده. کار با سود ۴۰ را برای اجرا در نوبت دوم انتخاب میکنیم. کار با سود ۲۰ قابل زمانبندی نیست، چون تنها در نوبت اول و دوم قابل اجراست، اما این دو نوبت قبلاً اشغال شدهاند. و ...
(۲۳ اسفند ۱۳۹۴ ۰۳:۲۵ ب.ظ)MShariati نوشته شده توسط: سلام.ممنون ولی ۱۷۰ تو گزینه ها نیس. جواب ۱۷۵ه. اگه میشه مفصلتر توضیح بدین. مثلن چرا ۴۰ قابل زمانبندی هس ولی ۴۵نه؟؟؟
الگوریتم حریصانه:
کارها رو به ترتیب سود غیرصعودی مرتب کنید و با شروع از بیشترین سود، هر کار رو در دیرترین مهلت ممکن زمانبندی کنید.
لیست کارها به ترتیب سود:
۶۰-۵۵-۴۵-۴۰-۲۰-۱۵-۱۰
اگه مهلتها رو درست خونده باشم:
۱ ۱ ۳ ۲ ۳ ۴ ۲ → مهلتها
به راحتی میشه فهمید که جواب ۱۷۰ خواهد بود. سود کارهای انتخاب شده: ۱۵ + ۴۰ + ۵۵ + ۶۰
ابتدا کار با سود ۶۰ را برای اجرا در نوبت سوم انتخاب میکنیم. بعد کار با سود ۵۵ را برای اجرا در نوبت اول انتخاب میکنیم. کار با سود ۴۵ قابل زمانبندی نیست، چون تنها در نوبت اول قابل اجراست ولی این نوبت قبلاً اشغال شده. کار با سود ۴۰ را برای اجرا در نوبت دوم انتخاب میکنیم. کار با سود ۲۰ قابل زمانبندی نیست، چون تنها در نوبت اول و دوم قابل اجراست، اما این دو نوبت قبلاً اشغال شدهاند. و ...
توضیح این الگوریتم حریصانه همون یک خطه که گفتم، شما به همون که عمل کنید به جواب درست میرسید.
بقیهاش trace الگوریتمه روی این مسئلهی خاص، شایدم مهلتها رو درست نخوندم.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.