الگوریتم حریصانه

[19216810047]

با سلام خدمت دوستان

بچه ها من می خوام مسیله زیر رو با روش حریصانه حل کنم.(اما مسیله یه کمی سخته)کسی می تونه منو راهنمایی کنه.با تشکر

مسیله:

استاد طراحی الگوریتم می خواهد nتمرین به دانش اموزان بدهد و برای هر تمرین مشخص کرده که حد اکثر در چه روزی پس از شروع ترم می توان ان را تحویل داد .نکته ای که در روش تدریس این استاد مهربان وجود دارد این است که
تحویل به موقع تمرین iام نمره ای ندارد ولی اگر از تاریخ مشخص شده بگذرد به اندازه piنمره ازنمره نهایی دانش اموز کسر می شود. یک دانش اموز تیز هوش برای حل کردن هر تمرین یک روز زمان نیاز دارد. الگورینمی بهینه طراحی کنید که مشخص کند که این دانشجو هر تمرین را در چه روزی حل کند و تحویل دهد تا کمترین میزان نمره از او کسر شود.درستی الگوریتم را اثبات کنید.

[ehsan_68]

سلام
اگر این مسئله همون مسئله معروف Greedy باشه، روش اینه که هر تمرین رو دقیقا قبل از روز تحویل انجام دهد. در صورتی که پر بود، روز قبل آن و به همین ترتیب ...
اثباتش هم مثل تمام مسائل Greedy ـه!

[19216810047]

میشه یه خورده بیشتر توضیح بدی ؟
با تشکر.

[ehsan_68]

سلام
مثلا فرض کنید یه تمرینی روز شماره 10 باشه تحویلش. شما بیاید چک کنید اگر روز 10 خالی بود، برای اون روز بذارید، اگر نبود روز 9 و همین طور بیاید عقب تا یه روز خالی پیدا کنید. به همین ترتیب همه ی تمرین ها زمان بندی می شن.
برای اثباتش هم فرض کنید این طور نیست، یعنی حالت بهینه حالتی است که یک تمرین در روز دیگری به غیر از روز آخر تحویل انجام شود و نشان دهید که این حالت، بهتر از حالتی که گفتیم نیست.

[bhossein]

سلام
مثلا فرض کنید یه تمرینی روز شماره 10 باشه تحویلش. شما بیاید چک کنید اگر روز 10 خالی بود، برای اون روز بذارید، اگر نبود روز 9 و همین طور بیاید عقب تا یه روز خالی پیدا کنید. به همین ترتیب همه ی تمرین ها زمان بندی می شن.

تا اینجا درست :تشویق:


اما نوشتار زیر یه جوریه که منظورتو من نمی فهمم؟!! :متعجب:
برای اثباتش هم فرض کنید این طور نیست، یعنی حالت بهینه حالتی است که یک تمرین در روز دیگری به غیر از روز آخر تحویل انجام شود و نشان دهید که این حالت، بهتر از حالتی که گفتیم نیست.
سوال قشنگی بود؟1