سود بیشینه در زمانبندی با مهلت

[Developer Programmer]

مثال 4-4 کتاب طراحی الگوریتم جعفرنژاد قمی، صفحه 150

چرا ترتیب 1و2و4 رو انتخاب میکنه ؟! (کار شماره یک بیشترین سود رو داره پس انتخاب میشه، در زمان دو، باید کار 7 انتخاب بشه، پس چرا کار 2 که مهلتش تمام شده، انتخاب میشه ؟)

[xxxxx_xxxxx]

سلام
دوست عزيز اگه امكانش هست سوال رو هم بنويسيد. اين طوري بهتره

[pesar irooni]

تورو خدا دیگه طراحی الگوریتم رو از کتاب جعفر نژاد نخونید.
روش حل باید برنامه نویسی حریصانه باشه. اول کاری رو انتخاب می کنیم که بیشترین سود رو داره و سپس اون رو تا آخرین لحظه ممکن عقب میندازیم. سودی که بدست بیاد بیشترینه. فقط باید توجه کرد که جواب یکتا نیست

[Developer Programmer]

عذر میخوام ولی اصلا متوجه نشدم! ممکنه بیشتر توضیح بدید؟

[Kensington]

کتابی که مرجع داده اید رو ندارم. پس صورت سوال رو هم ندارم! ای کاش فرصت میکردید و تایپش میکردید.

اما همین جوری از روی صورت سوال به نظرم رسید که باید چنین چیزی باشه:
فرصت محدودی داریم تا یک سری اجناس رو انتخاب کنیم و میخواهیم گرون ترین اجناس در این فرصت انتخاب شده باشه.

برای این سوال، اینطوری به فکرم میرسه:
اول اجناس رو مرتب کنیم بر حسب ارزششون از گرون ترین به ارزون ترین.
حالا ابتدا گرون ترین جنس رو انتخاب کنیم. در فرصت باقیمانده دوباره گرونترین جنس رو انتخاب میکنیم ( در واقع میشه دومین گرون ترین. ولی چون اولین گرون ترین رو دفعه اول انتخاب کرده ایم و دیگه وجود نداره . پس دوباره داریم همون اولین گرون ترین رو انتخاب میکنیم ) و ... ادامه ... تا وقتی وقت تمام شود.

طرز فکر greedy

[Developer Programmer]

بفرمایین این هم خود مساله

[xxxxx_xxxxx]

:متفکر::متفکر::متفکر:

[Developer Programmer]

جسارتا یک بار دیگه می پرسم:
چرا ترتیب 1و2و4 رو انتخاب میکنه ؟! (کار شماره یک بیشترین سود رو داره پس انتخاب میشه، در زمان دو، باید کار 7 انتخاب بشه، پس چرا کار 2 که مهلتش تمام شده، انتخاب میشه ؟)

[pesar irooni]

من حل میکنم جوابتون رو میدم.

[pesar irooni]

ببین دوست عزیز. شما اول کار 1 رو که بیشترین سود رو داره انتخاب می کنی و زمان 3 رو براش کنار میذاری (یعنی آخرین مهلتی که میتونه انجام بشه). بعد میری سراغ دومی که بیشترین سود رو داره یعنی کار 2 و آخرین مهلتی که میتونه انجام بشه یعنی زمان 1 رو به اون اختصاص میدی. بعد میری سراغ کار 3، میبینی که دیگه نمیتونی زمانی بهش اختصاص بدی چون مهلتش تموم شده و زمان 1 رو قبلا به کار با ارزش دیگه ای دادی. در آخر هم کار شماره 4 که بیشترین سود رو بین بقیه داره انتخاب میکنی و در زمان خالی 2 انجام میدی.

[amin noruzi]

اما کار شماره 4 زمانش 3 هست.قبلش نمیشه کار 7 رو انجام بده بعد کار شماره 4 رو؟
از طرفی کار شماره 1 زمانش 3 هست.مگه ممکنه کار 1 و 4 تو زمان 3 (یک زمان )انجام بشه؟