مثال 4-4 کتاب طراحی الگوریتم جعفرنژاد قمی، صفحه 150
چرا ترتیب 1و2و4 رو انتخاب میکنه ؟! (کار شماره یک بیشترین سود رو داره پس انتخاب میشه، در زمان دو، باید کار 7 انتخاب بشه، پس چرا کار 2 که مهلتش تمام شده، انتخاب میشه ؟)
سود بیشینه در زمانبندی با مهلت
مثال 4-4 کتاب طراحی الگوریتم جعفرنژاد قمی، صفحه 150
چرا ترتیب 1و2و4 رو انتخاب میکنه ؟! (کار شماره یک بیشترین سود رو داره پس انتخاب میشه، در زمان دو، باید کار 7 انتخاب بشه، پس چرا کار 2 که مهلتش تمام شده، انتخاب میشه ؟)
سلام
دوست عزيز اگه امكانش هست سوال رو هم بنويسيد. اين طوري بهتره
الگوریتم هایی که تاریخچه خود را فراموش می کنند، محکوم به تکرار آن هستند.
تورو خدا دیگه طراحی الگوریتم رو از کتاب جعفر نژاد نخونید.
روش حل باید برنامه نویسی حریصانه باشه. اول کاری رو انتخاب می کنیم که بیشترین سود رو داره و سپس اون رو تا آخرین لحظه ممکن عقب میندازیم. سودی که بدست بیاد بیشترینه. فقط باید توجه کرد که جواب یکتا نیست
عذر میخوام ولی اصلا متوجه نشدم! ممکنه بیشتر توضیح بدید؟
کتابی که مرجع داده اید رو ندارم. پس صورت سوال رو هم ندارم! ای کاش فرصت میکردید و تایپش میکردید.
اما همین جوری از روی صورت سوال به نظرم رسید که باید چنین چیزی باشه:
فرصت محدودی داریم تا یک سری اجناس رو انتخاب کنیم و میخواهیم گرون ترین اجناس در این فرصت انتخاب شده باشه.
برای این سوال، اینطوری به فکرم میرسه:
اول اجناس رو مرتب کنیم بر حسب ارزششون از گرون ترین به ارزون ترین.
حالا ابتدا گرون ترین جنس رو انتخاب کنیم. در فرصت باقیمانده دوباره گرونترین جنس رو انتخاب میکنیم ( در واقع میشه دومین گرون ترین. ولی چون اولین گرون ترین رو دفعه اول انتخاب کرده ایم و دیگه وجود نداره . پس دوباره داریم همون اولین گرون ترین رو انتخاب میکنیم ) و ... ادامه ... تا وقتی وقت تمام شود.
طرز فکر greedy
بفرمایین این هم خود مساله
الگوریتم هایی که تاریخچه خود را فراموش می کنند، محکوم به تکرار آن هستند.
جسارتا یک بار دیگه می پرسم:چرا ترتیب 1و2و4 رو انتخاب میکنه ؟! (کار شماره یک بیشترین سود رو داره پس انتخاب میشه، در زمان دو، باید کار 7 انتخاب بشه، پس چرا کار 2 که مهلتش تمام شده، انتخاب میشه ؟)
من حل میکنم جوابتون رو میدم.
ببین دوست عزیز. شما اول کار 1 رو که بیشترین سود رو داره انتخاب می کنی و زمان 3 رو براش کنار میذاری (یعنی آخرین مهلتی که میتونه انجام بشه). بعد میری سراغ دومی که بیشترین سود رو داره یعنی کار 2 و آخرین مهلتی که میتونه انجام بشه یعنی زمان 1 رو به اون اختصاص میدی. بعد میری سراغ کار 3، میبینی که دیگه نمیتونی زمانی بهش اختصاص بدی چون مهلتش تموم شده و زمان 1 رو قبلا به کار با ارزش دیگه ای دادی. در آخر هم کار شماره 4 که بیشترین سود رو بین بقیه داره انتخاب میکنی و در زمان خالی 2 انجام میدی.
اما کار شماره 4 زمانش 3 هست.قبلش نمیشه کار 7 رو انجام بده بعد کار شماره 4 رو؟
از طرفی کار شماره 1 زمانش 3 هست.مگه ممکنه کار 1 و 4 تو زمان 3 (یک زمان )انجام بشه؟
قوانین ایجاد تاپیک در تالار
پاسخ با نقل قول