موضوع مقاله: فهرست مسائل کوله‌پشتی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # فهرست مسائل کوله‌پشتی | مقدمه: مسئله کوله‌پشتی، یکی از مسائل مورد مطالعه در بهینه سازی ترکیبیاتی است که در بعضی موارد در زندگی واقعی نیز کاربرد دارد. | ## بخش 1: فهرست مسائل کوله‌پشتی | چیزی که در تمام نسخه‌های این مسئله مشترک است، وجود مجموعه‌ای با n عضو است، که هر عضو با اندیس j که ، یک ارزش و وزن دارد. هدف برداشتن تعدادی از اعضا است، به طوری که ارزش کلشان بیشینه شود و در عین حال بیشینه مجموع وزن اشیا انتخاب‌شده از تجاوز نکند. در حالت کلی، این ضرایب در عددی ضرب می‌شوند (مقیاس می‌شوند) تا به اعداد صحیح تبدیل شوند و همیشه فرض می‌شود که این ضرایب عدد طبیعی هستند. مسئله کوله‌پشتی در ساده‌ترین شکل به صورت زیر است: را بیشینه کنید، به طوری‌که ،،. کلی‌سازی مستقیم یک شکل رایج این مسئله این است که هر عضو بتواند چندین بار انتخاب شود. مسئله کوله‌پشتی محدود برای هر عضو ، یک کران بالای (که می‌تواند یک عدد صحیح مثبت یا بی‌نهایت باشد.) که تعداد دفعاتی است که عضو ام انتخاب شده‌است را مشخص می‌کند: را بیشینه کنید، به طوری‌که ، و برای هر عددی صحیح است. مسئله کوله‌پشتی نامحدود (که گاهی اوقات مسئله کوله‌پشتی صحیح نیز خوانده می‌شود) برای تعداد تکرارهای یک عضو کران بالایی قرار نمی‌دهد: را بیشینه کنید، به طوری‌که و ، برای هر j عددی صحیح است. هر دو نوع محدود و نامحدود این مسئله یک FPTAS دارند (در اصل شبیه به همان است که در مسئله کوله‌پشتی 0-1 استفاده شد). | ## بخش 2: فهرست مسائل کوله‌پشتی | اگر اعضا در k دسته که با نشان داده می‌شوند طبقه بندی شوند، و دقیقاً از هر کلاس یک عضو انتخاب شود آنگاه با مسئله کوله‌پشتی چند گزینه ای روبرو هستیم: را بیشینه کنید، به طوری‌که ؛ ، برای هر و ، برای هر و هر . اگر برای هر عضو ارزش و وزنش یکسان باشند، با مسئله جمع زیرمجموعه ها روبرو هستیم (اغلب مسئله تصمیم که متناظر با آن است به جای آن داده می‌شود): را بیشینه کنید، به طوری‌که ، . اگر n عضو و m کوله‌پشتی با ظرفیت داشته باشیم،با مسئله کوله‌پشتی چندگانه روبرو هستیم: را بیشینه کنید، به طوریکه ، برای هر و ، برای هر و ، برای هر و هر . به عنوان یک حالت خاصِ مسئله کوله‌پشتی چندگانه، هنگامی که ارزش‌ها با وزن‌ها برابر و همه صندوق‌ها حجم برابر داشته باشند، با مسئله حاصل جمع زیرمجموعه‌های چندگانه روبرو هستیم: مسئله کوله‌پشتی درجه دوم: را بیشینه کنید، به طوری‌که ، برای هر . مسئله کوله‌پشتی مجموعه-اجتماع(SUKP): SUKP توسط Kellerer و همکارانش ( در صفحه 423) همانطور که در ادامه آمده تعریف شده‌است: مجموعه شامل عضو و شامل عضو داده شده است، هر عضو به یک زیرمجموعه از مجموعه مربوط میشود. هدف پیدا کردن زیرمجموعه ای از عضوها است که وزن کلی آن از حجم کوله‌پشتی بیشتر نشود و ارزش بیشینه را داشته باشد. محدودیت چندگانه اگر بیشتر از یک محدودیت وجود داشته‌باشد (برای مثال هم محدودیت حجمی و هم محدودیت وزنی داشته‌باشیم، در حالی‌که حجم و وزن هر شی هیچ رابطه‌ای با یکدیگر ندارند)، به مسئلهٔ کوله‌پشتی با شرایط چندگانه، مسئله کوله‌پشتی چند بعدی، یا مسئله کوله‌پشتی m- بعدی می‌رسیم (توجه کنید که "بُعد" در این‌جا هیچ ارتباطی به شکل اشیا ندارد). این مسئله انواع 0-1، محدود و نامحدود دارد که نوع نامحدود آن در زیر نشان داده شده‌است: را بیشینه کنید، به طوریکه ، برای هر ، برای هر عددی صحیح باشد. | ## بخش 3: فهرست مسائل کوله‌پشتی | در حدود سال 1980 نشان داده شد که نوع 0-1 مسئله (برای هر ثابت) ان‌پی کامل است و به‌طور قویتر FPTAS ندارد مگر اینکه P = NP. برای هر ثابت، این مسائل یک زمان اجرای شبه چندجمله‌ای (مشابه مسئله کوله‌پشتی اصلی) و یک PTAS دارند. مسئله‌های مشابه کوله‌پشتی اگر ارزش همهٔ اشیا یک باشد می‌توانیم تلاش کنیم تا تعداد اشیایی که کوله‌پشتی را کاملاً پر می‌کنند، کمینه کنیم: را کمینه کنید، به طوریکه و ، . اگر تعدادی جعبه (با سایز یکسان) داشته باشیم و هدف قرار دادن همهٔ n شی در حداقل تعداد جعبه ممکن باشد به مسللهٔ bin packing (بسته بندی جعبه ها) می‌رسیم که با متغیرهای شاخص مدل می‌شود و است اگر و تنها اگر جعبهٔ iم استفاده شود: را کمینه کنید، به طوریکه ، و ، و ، و ، . عضو jم مرتبه نیاز است، هر الگویی از اعضا که برای یک کوله‌پشتی مناسب باشد یک متغیر دارد(m الگو وجود دارد) و الگوی i عضو j را بار استفاده می‌کند: را کمینه کنید، به طوریکه برای هر و برای هر . اگر برای مسئله کوله‌پشتی چندگزینه‌ای که در آن‌ها چند انتخاب وجود دارد، این محدودیت که در آن سایز هر زیرمجموعه n باشد را اضافه کنیم و محدودیت بر روی وزن کلی را حذف کنیم، به مسئلهٔ assignment می‌رسیم که مسئلهٔ پیدا کردن یک جور سازی دوبخشی بیشینه نیز است: را بیشینه کنید، به طوریکه برای هر و برای هر و برای هر و برای هر . در مسئله کوله‌پشتی با چگالی بیشینه وزن اولیه است و ما تراکم اشیای انتخابی را تا زمانی‌که با محدودیت‌های ظرفیت مغایرت نداشته باشد، زیاد می‌کنیم:Cohen, R. | ## جمع‌بندی | تعداد دیگری مسئله‌های مشابه کوله‌پشتی نیز وجود دارند که البته نسبت به مسئله‌های ذکرشده کمتر متداول هستند، شامل: مسئله کوله‌پشتی تو در تو مسئله کوله‌پشتی سقوط‌کننده مسئله کوله‌پشتی غیرخطی مسئله کوله‌پشتی معکوس پارامتری سه مسئلهٔ آخر در مرجع کار کلرر و همکارانش، مشکلات کوله پشتی، مورد بحث و بررسی قرار گرفته‌اند.