پاورپوینت با عنوان یادآوری مسئله کوله پشتی صفر و یک

لینک دانلود و خرید پایین توضیحات
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (..pptx) ( قابل ویرایش و آماده پرینت )
تعداد صفحه : 19 صفحه

قسمتی از متن PowerPoint (..pptx) :

اهداف درس این جلسه حل مساله کوله پشتی با رویکرد حریصانه مقایسه رویکرد حریصانه با برنامه نویسی پویا در حل مساله که wi و pi و W همگی اعداد مثبتی هستند. می خواهیم زیر مجموعه A از S را به گونه ای مشخص کنیم که ... 3 یادآوری مسئله کوله پشتی صفر و یک ه) الگوریتم حریصانه در مسئله کوله پشتی صفر و یک اگر بخواهیم رویکرد brute-force را درنظر بگیریم ... باید تمامی زیرمجموعه های S را درنظر بگیریم و ... از اونهایی که مجموع وزنشون از W بیشتر است صرفنظر کنیم و ... از زیرمجموعه های باقیمانده اونی که بیشترین مجموع منفعت دارد را به عنوان پاسخ انتخاب کنیم. پیچیدگی محاسباتی این روش بادرنظر گرفتن n آیتم .... 2n می باشد 4 ه) الگوریتم حریصانه در مسئله کوله پشتی صفر و یک اولین راه حل حریصانه که شاید برای این مساله به ذهن برسد آن است که ... تمامی آیتم ها را بر اساس منفعتشان به صورت نزولی مرتب کنیم و ... به ترتیب آیتم ها را از مجموعه مرتب شده برداریم مادامیکه ... مجموع وزنشان از W بیشتر نشود. این استراتژی زمانیکه آیتم های با منفعت بالا وزن بیشتری در مقایسه با منفعتشون دارند مناسب نمی باشد. 5