جواب صحیح گزینه ۲ هست.
به نظر من با روش تقسیم وحل میشه این مساله رو در زمان nlogn حل کرد.
یعنی اول طول L هست بعد تیر رو از وسط نصف کنیم و به صورت بازگشتی این عمل تکرار بشه.
تو این مساله که زیر مسائل هم پوشانی ندارن که با پویا حل بشه!
توجه کنید که L ها مساوی نیستن! پس نصف کردن L کاری رو پیش نمیبره، به نظر من این مسئله بیشتر شبیه کوله پشتی هستش و از راه پویا حل میشه، طول کل مثل ظرفیت کوله پشتی و l1 تا ln اشیاءی که میخوایم انتخاب کنیم (میشه اندازه هارو به ترتیب صعودی (یا نزولی )مرتب کرد و یکی یکی انتخابشون کرد)
(۰۱ بهمن ۱۳۸۹ ۰۳:۰۴ ب.ظ)hamidkhl نوشته شده توسط: توجه کنید که L ها مساوی نیستن! پس نصف کردن L کاری رو پیش نمیبره،
متوجه نمیشم!
به مساوی بودن ربطی نداره که !
(۰۱ بهمن ۱۳۸۹ ۰۳:۰۴ ب.ظ)hamidkhl نوشته شده توسط: به نظر من این مسئله بیشتر شبیه کوله پشتی هستش و از راه پویا حل میشه، طول کل مثل ظرفیت کوله پشتی و l1 تا ln اشیاءی که میخوایم انتخاب کنیم (میشه اندازه هارو به ترتیب صعودی (یا نزولی )مرتب کرد و یکی یکی انتخابشون کرد)کوله پشتی ۰و۱ راه حل پویا داره، کوله پشتی کسری راه حل حریصانه.
شما گفتی پویا ولی روشی که ارائه دادین حریصانه هست.
تو مساله کوله پشتی اصل بهینگی برقراره یعنی اگر یک زیرمجموعه n تایی انتخاب کنی که بیشترین سود رو داره این مجموعه شامل زیرمجموعه n-1 تایی که بیشترین سود رو داره میشه.
به نظر من شبیه کوله پشتی نیس چون اونجا نمونه های کوچک با هم مرتبط هستند.
فرق پویا با تقسیم و حل اینکه تو پویا زیرمسائل با هم مرتبط هستند و شباهتشون اینکه هر دو شون باید یک رابطه بازگشتی داشته باشند.
ما وقتی از پویا به جای تقسیم و حل استفاده میکنیم که نمونه های کوچکتر مساله با هم مرتبط باشند.
اینجا چه جوری نمونه های کوچک با هم مربوطند؟
فکر کنم این مساله همون مساله برش میله تو کتاب clrs باشه.که از روش تقسیم و حل شده نمایی و از روش پویا شده n^2
این مسئله یکی از مسایل کلاسیک الگوریتم‍های پویا است. دکتر قدسی این سوال‍ها رو بارها در تمرین‍های کارشناسی به بچه‍ها می‍دن. من مجموعه‍ای از این سوالات رو لینک می‍دم که آشنا بشید.:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
صفحه ۳۷۲ ترجمه انتشارت نص.میشه اولین مبحث تو فصل برنامه نویسی پویا.
(۰۳ بهمن ۱۳۸۹ ۰۴:۵۴ ق.ظ)admin نوشته شده توسط: این مسئله یکی از مسایل کلاسیک الگوریتم‍های پویا است. دکتر قدسی این سوال‍ها رو بارها در تمرین‍های کارشناسی به بچه‍ها می‍دن. من مجموعه‍ای از این سوالات رو لینک می‍دم که آشنا بشید.:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
جناب دکتر ممنون از توجهتون. اما فایل گویا خرابه. به من پیغام damage file میده. اگر ممکنه اصلاحش کنید.
فایل بررسی شد و عدم اشکالش تایید میشه
فایل برای من هم error داد.
فایل سالمه.برای من که Error نداد.
من حتی save target as هم کردم ولی باز نشد!!
فشرده شده در لینک زیر آپلود شد:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
این سوال معروف خط کش در حالت خاص دارای الگوریتم پویاست در حالت کلی تر np و الگوریتم تقریبی مناسبی حریصانه دارد