پاورپوینت یادآوری مسئله کوله‌پشتی صفر و یک (pptx) 19 اسلاید
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید: 19 اسلاید
قسمتی از متن PowerPoint (.pptx) :
اهداف درس این جلسه
حل مساله کوله پشتی با رویکرد حریصانه
مقایسه رویکرد حریصانه با برنامه‌نویسی پویا در حل مساله
که wi و pi و W همگی اعداد مثبتی هستند. می‌خواهیم زیر مجموعه A از S را به گونه‌ای مشخص کنیم که ...
3
یادآوری مسئله کوله‌پشتی صفر و یک
ه) الگوریتم حریصانه در مسئله کوله پشتی صفر و یک
اگر بخواهیم رویکرد brute-force را درنظر بگیریم ...
باید تمامی زیرمجموعه‌های S را درنظر بگیریم و ...
از اونهایی که مجموع وزنشون از W بیشتر است صرفنظر کنیم و ...
از زیرمجموعه‌های باقیمانده اونی که بیشترین مجموع منفعت دارد را به عنوان پاسخ انتخاب کنیم.
پیچیدگی محاسباتی این روش بادرنظر گرفتن n آیتم ....
2n میباشد
4
ه) الگوریتم حریصانه در مسئله کوله پشتی صفر و یک
اولین راه حل حریصانه که شاید برای این مساله به ذهن برسد آن است که ...
تمامی آیتم‌ها را بر اساس منفعتشان به صورت نزولی مرتب کنیم و ...
به ترتیب آیتم‌ها را از مجموعه مرتب‌شده برداریم مادامیکه ...
مجموع وزنشان از W بیشتر نشود.
این استراتژی زمانیکه آیتم‌های با منفعت بالا وزن بیشتری در مقایسه با منفعتشون دارند مناسب نمی‌باشد.
5
ه) الگوریتم حریصانه در مسئله کوله پشتی صفر و یک
احتمالا استراتژی بعدی این می‌تواند باشد که آیتم‌های سبک‌تر را ابتدا برداریم ...
این استراتژی هم زمانی که آیتم‌های سبک منفعت کمی داشته باشند به شکست می‌انجامد.
6
ه) الگوریتم حریصانه در مسئله کوله پشتی صفر و یک
راه حل حریصانه مناسب این است که ...
آیتم‌ها را بر اساس منفعت واحد وزنشان به صورت نزولی مرتب کنیم و ...
آیتم‌ها را تا زمانیکه مجموع وزنشان از W بیشتر نشود برداریم.
7
ه) الگوریتم حریصانه در مسئله کوله پشتی صفر و یک
8
ه) الگوریتم حریصانه در مسئله کوله پشتی کسری (Fractional)
در مساله کوله‌پشتی کسری چنانچه برداشتن کل آیتم میسر نیست، می‌توان بخشی از آن را نیز برداشت.
مثلا در مثال قبل ...
بنابراین هیچ فضایی هدر نمی‌رود.
پس همواره حل بهینه را خواهیم داشت.
9
