فهرست مسائل کوله‌پشتی کیست؟ توضیح بده.
مسئله کوله‌پشتی، یکی از مسائل مورد مطالعه در بهینه سازی ترکیبیاتی است که در بعضی موارد در زندگی واقعی نیز کاربرد دارد. به همین دلیل تعدادی از حالات خاص یا حالات کلی آن مورد آزمایش قرار گرفته‌است.چیزی که در تمام نسخه‌های این مسئله مشترک است، وجود مجموعه‌ای با n عضو است، که هر عضو با اندیس j که formula_1، یک ارزش formula_2 و وزن formula_3 دارد. متغیر دودویی تصمیم formula_4 برای انتخاب کردن اشیا به کار میرود. هدف برداشتن تعدادی از اعضا است، به طوری که ارزش کلشان بیشینه شود و در عین حال بیشینه مجموع وزن اشیا انتخاب‌شده از formula_5 تجاوز نکند. در حالت کلی، این ضرایب در عددی ضرب می‌شوند (مقیاس می‌شوند) تا به اعداد صحیح تبدیل شوند و همیشه فرض می‌شود که این ضرایب عدد طبیعی هستند.مسئله کوله‌پشتی در ساده‌ترین شکل به صورت زیر است:formula_6 را بیشینه کنید، به طوری‌که formula_7،formula_8،formula_9.کلی‌سازی مستقیم.یک شکل رایج این مسئله این است که هر عضو بتواند چندین بار انتخاب شود. مسئله کوله‌پشتی محدود برای هر عضو formula_10، یک کران بالای formula_11 (که می‌تواند یک عدد صحیح مثبت یا بی‌نهایت باشد.) که تعداد دفعاتی است که عضو formula_10ام انتخاب شده‌است را مشخص می‌کند:formula_6 را بیشینه کنید، به طوری‌که formula_7، formula_15 وformula_4 برای هر formula_10 عددی صحیح است.مسئله کوله‌پشتی نامحدود (که گاهی اوقات مسئله کوله‌پشتی صحیح نیز خوانده می‌شود) برای تعداد تکرارهای یک عضو کران بالایی قرار نمی‌دهد:formula_6 را بیشینه کنید، به طوری‌که formula_7 و formula_20، formula_21 برای هر j عددی صحیح است.در سال 1975 لوکر ثابت کرد که نوع نامحدود مسئله ان‌پی کامل است. هر دو نوع محدود و نامحدود این مسئله یک FPTAS دارند (در اصل شبیه به همان است که در مسئله کوله‌پشتی 0-1 استفاده شد).اگر اعضا در "k" دسته که با formula_22 نشان داده می‌شوند طبقه بندی شوند، و دقیقاً از هر کلاس یک عضو انتخاب شود آنگاه با مسئله کوله‌پشتی چند گزینه ای روبرو هستیم:formula_23را بیشینه کنید، به طوری‌که formula_24 ؛ formula_25، برای هر formula_26و formula_27، برای هرformula_26 و هر formula_29.اگر برای هر عضو ارزش و وزنش یکسان باشند، با مسئله جمع زیرمجموعه ها روبرو هستیم (اغلب مسئله تصمیم که متناظر با آن است به جای آن داده می‌شود):formula_6را بیشینه کنید، به طوری‌که formula_31، formula_8.اگر "n" عضو و "m" کوله‌پشتی با ظرفیت formula_33 داشته باشیم،با مسئله کوله‌پشتی چندگانه روبرو هستیم:formula_34را بیشینه کنید، به طوریکه formula_35، برای هر formula_36و formula_37، برای هر formula_1و formula_27، برای هر formula_1 و هر formula_36.به عنوان یک حالت خاصِ مسئله کوله‌پشتی چندگانه، هنگامی که ارزش‌ها با وزن‌ها برابر و همه صندوق‌ها حجم برابر داشته باشند، با مسئله حاصل جمع زیرمجموعه‌های چندگانه روبرو هستیم:مسئله کوله‌پشتی درجه دوم:formula_42 را بیشینه کنید، به طوری‌که formula_7،formula_8برای هرformula_1.مسئله کوله‌پشتی مجموعه-اجتماع(SUKP):SUKP توسط Kellerer و همکارانش ( در صفحه 423) همانطور که در ادامه آمده تعریف شده‌است:مجموعه formula_46 شامل formula_47 عضو و formula_48 شامل formula_49 عضو داده شده است، هر عضو formula_10 به یک زیرمجموعه formula_51 از مجموعه formula_52 مربوط میشود. برای هرformula_53 ، عضو formula_10ام ارزش نامنفی formula_2 دارد، و برای هر formula_56 ، عضو formula_57 ام وزن نامنفی formula_58 دارد. وزن کلی یک مجموعه از اعضا برابر با مجموع وزن اعضای متناظر آن در مجموعه است. هدف پیدا کردن زیرمجموعه ای از عضوها است که وزن کلی آن از حجم کوله‌پشتی بیشتر نشود و ارزش بیشینه را داشته باشد.محدودیت چندگانه.اگر بیشتر از یک محدودیت وجود داشته‌باشد (برای مثال هم محدودیت حجمی و هم محدودیت وزنی داشته‌باشیم، در حالی‌که حجم و وزن هر شی هیچ رابطه‌ای با یکدیگر ندارند)، به مسئلهٔ کوله‌پشتی با شرایط چندگانه، مسئله کوله‌پشتی چند بعدی، یا مسئله کوله‌پشتی m- بعدی می‌رسیم (توجه کنید که "بُعد" در این‌جا هیچ ارتباطی به شکل اشیا ندارد). این مسئله انواع 0-1، محدود و نامحدود دارد که نوع نامحدود آن در زیر نشان داده شده‌است:formula_6را بیشینه کنید، به طوریکهformula_60، برای هرformula_61formula_62، formula_4 برای هر formula_64 عددی صحیح باشد.در حدود سال 1980 نشان داده شد که نوع 0-1 مسئله (برای هر formula_65 ثابت) ان‌پی کامل است و به‌طور قویتر FPTAS ندارد مگر اینکه P = NP.انواع محدود و نامحدود مسئله نیز (برای هرformula_65 ثابت) درجه سختی مشابه دارند.برای هر formula_65 ثابت، این مسائل یک (مشابه مسئله کوله‌پشتی اصلی) و یک PTAS دارند.مسئله‌های مشابه کوله‌پشتی.اگر ارزش همهٔ اشیا یک باشد می‌توانیم تلاش کنیم تا تعداد اشیایی که کوله‌پشتی را کاملاً پر می‌کنند، کمینه کنیم:formula_68 را کمینه کنید، به طوریکه formula_69 وformula_8،formula_71.اگر تعدادی جعبه (با سایز یکسان) داشته باشیم و هدف قرار دادن همهٔ n شی در حداقل تعداد جعبه ممکن باشد به مسللهٔ (بسته بندی جعبه ها) می‌رسیم که با متغیرهای شاخص مدل می‌شود و formula_72 است اگر و تنها اگر جعبهٔ "i"م استفاده شود:formula_73را کمینه کنید، به طوریکهformula_74،formula_75و formula_76، formula_77و formula_78، formula_75و formula_27، formula_81.مسئلهٔ مشابه مسئلهٔ است، اما از آن‌جا که نمونه‌های عملی انواع کمتری از اعضا دارند، اغلب از فرمول دیگری استفاده می‌شود. عضو "j"م formula_82 مرتبه نیاز است، هر الگویی از اعضا که برای یک کوله‌پشتی مناسب باشد یک متغیر formula_83 دارد("m" الگو وجود دارد) و الگوی "i" عضو "j" را formula_84 بار استفاده می‌کند:formula_85را کمینه کنید، به طوریکهformula_86برای هر formula_1و formula_88برای هرformula_89.اگر برای مسئله کوله‌پشتی چندگزینه‌ای که در آن‌ها چند انتخاب وجود دارد، این محدودیت که در آن سایز هر زیرمجموعه "n" باشد را اضافه کنیم و محدودیت بر روی وزن کلی را حذف کنیم، به مسئلهٔ assignment می‌رسیم که مسئلهٔ پیدا کردن یک بیشینه نیز است:formula_90را بیشینه کنید، به طوریکهformula_76برای هر formula_1و formula_93برای هرformula_94و formula_27برای هر formula_26 و برای هر formula_29.در مسئله کوله‌پشتی با چگالی بیشینه وزن اولیه formula_98 است و ما تراکم اشیای انتخابی را تا زمانی‌که با محدودیت‌های ظرفیت مغایرت نداشته باشد، زیاد می‌کنیم:formula_99را بیشینه کنید، به طوریکهformula_7 و formula_8، formula_71.تعداد دیگری مسئله‌های مشابه کوله‌پشتی نیز وجود دارند که البته نسبت به مسئله‌های ذکرشده کمتر متداول هستند، شامل:سه مسئلهٔ آخر در مرجع کار کلرر و همکارانش، مشکلات کوله پشتی، مورد بحث و بررسی قرار گرفته‌اند.