(۰۱ بهمن ۱۳۸۹ ۰۳:۰۴ ب.ظ)hamidkhl نوشته شده توسط: توجه کنید که L ها مساوی نیستن! پس نصف کردن L کاری رو پیش نمیبره،
متوجه نمیشم!
به مساوی بودن ربطی نداره که !
(۰۱ بهمن ۱۳۸۹ ۰۳:۰۴ ب.ظ)hamidkhl نوشته شده توسط: به نظر من این مسئله بیشتر شبیه کوله پشتی هستش و از راه پویا حل میشه، طول کل مثل ظرفیت کوله پشتی و l1 تا ln اشیاءی که میخوایم انتخاب کنیم (میشه اندازه هارو به ترتیب صعودی (یا نزولی )مرتب کرد و یکی یکی انتخابشون کرد)
کوله پشتی ۰و۱ راه حل پویا داره، کوله پشتی کسری راه حل حریصانه.
شما گفتی پویا ولی روشی که ارائه دادین حریصانه هست.
تو مساله کوله پشتی اصل بهینگی برقراره یعنی اگر یک زیرمجموعه n تایی انتخاب کنی که بیشترین سود رو داره این مجموعه شامل زیرمجموعه n-1 تایی که بیشترین سود رو داره میشه.
به نظر من شبیه کوله پشتی نیس چون اونجا نمونه های کوچک با هم مرتبط هستند.
فرق پویا با تقسیم و حل اینکه تو پویا زیرمسائل با هم مرتبط هستند و شباهتشون اینکه هر دو شون باید یک رابطه بازگشتی داشته باشند.
ما وقتی از پویا به جای تقسیم و حل استفاده میکنیم که نمونه های کوچکتر مساله با هم مرتبط باشند.
اینجا چه جوری نمونه های کوچک با هم مربوطند؟
