مسئله کوله‌پشتی
تعریف

فرض کنید که جهانگردی می‌خواهد کوله‌پشتی خود را با انتخاب حالت‌های ممکن از بین وسائل گوناگونی که بیشترین راحتی را برایش فراهم می‌سازند پر کند. این مسئله می‌تواند با شماره‌گذاری این وسائل از ۱ تا n و تعریف برداری از متغیرهای دودویی (Binary) (j = ۱٬۲٬۳…n) به صورت ریاضی فرمول بندی شود. به این معنی که: اگر شیء j ام انتخاب شود در غیر اینصورت وقتی میزان راحتی باشد که وسیله j ا م فراهم می‌آورد و وزن آن و c اندازه کوله‌پشتی باشد. مسئله ما انتخاب برداری از بین بردارهای دودویی x است که محدودیت را برآورده کند. بطوری‌که تابع هدف، بیشترین مقدار خود را بگیرد به عنوان نمونه‌ای از مسائلی که می‌توانند به صورت مسئله کوله‌پشتی فرمول بندی شوند، مسئله زیر را در نظر بگیرید: فرض کنید که شما مایل به سرمایه‌گذاری همه یا قسمتی از سرمایه‌تان باشید. اگر مبلغی که برای سرمایه‌گذاری در نظر گرفتید c دلار باشد و n مورد برای سرمایه‌گذاری ممکن باشد، اجازه دهید که سود حاصل از سرمایه‌گذاری j ام و مقدار دلارهایی باشد که آن سرمایه‌گذاری لازم دارد. بدین ترتیب جواب بهینه مسئله کوله‌پشتی که تعریف کردیم به ما این امکان را می‌دهد که بهترین حالت ممکن را از بین حالت‌های گوناگون سرمایه‌گذاری انتخاب کنیم. در این رابطه باید روشی برای حل این مسئله پیدا کرد. یک روش ابتدایی که در نگاه نخست، توجه ما را به خود جلب می‌کند عبارت از برنامه‌نویسی برای رایانه به منظور امتحان کردن همه بردارهای دودویی ممکن x است، تا از بین بردارهایی که محدودیت مسئله را ارضاء می‌کنند بهترین را انتخاب کند. متأسفانه تعداد چنین بردارهایی است. بطوری‌که یک رایانه فرضی که می‌تواند یک بیلیون بردار را در یک ثانیه امتحان کند؛ برای n = ۶۰ بیش از ۳۰ سال وقت لازم دارد و بیش از ۶۰ سال برای n = ۶۱ و ده‌ها سده برای n = ۶۵ والی آخر. با این وجود با استفاده از الگوریتم‌هایی خاص می‌توان در بسیاری موارد مسئله‌ای با n = ۱۰۰ ۰۰۰ را در عرض چند ثانیه روی یک رایانه کوچک حل کرد.
فرض کنید  n جسم داریم که از  1 تا  n شماره‌گذاری شده‌اند. جسم  i ام ارزشی معادل  v_{i}و وزنی برابر با  w_{i} دارد. معمولاً فرض می‌شود که وزن‌ها و ارزش‌ها نامنفی‌اند. برای ساده‌تر شدن نمایش، بدون کم شدن از کلیت مسئله می‌توان فرض کرد اشیا به ترتیب صعودی بر حسب وزنشان مرتب شده‌اند. بیشترین وزنی که می‌توان در کوله‌پشتی حمل کرد، W است.
شناخته‌شده‌ترین نوع از این مسئله مسئلهٔ کوله‌پشتی ۰ و ۱ است؛ یعنی تعداد از هر شی، یا ۰ است (آن شی را انتخاب نمی‌کنیم) یا ۱ (آن شی انتخاب می‌شود). مسئلهٔ کوله‌پشتی ۰ و ۱ را می‌توان به این صورت، به زبان ریاضی بیان کرد:
مقدار  \qquad \sum _{i=1}^{n}v_{i}x_{i} را بیشینه کنید.
به‌طوری‌که  \qquad \sum _{i=1}^{n}w_{i}x_{i}\leqslant W,\quad x_{i}\in \{0,1\}
مسئلهٔ کوله‌پشتی کران‌دار نسخهٔ دیگری از این سؤال است که در آن تعداد اشیا ( x_{i}) عددی صحیح و نامنفی و حداکثر برابر با c_{i} است. به بیان ریاضی:
مقدار  \qquad \sum _{i=1}^{n}v_{i}x_{i}را بیشینه کنید.
به‌طوری که \qquad \sum _{i=1}^{n}w_{i}x_{i}\leqslant W,\quad x_{i}\in \{0,1,\ldots ,c_{i}\}
مسئلهٔ کوله‌پشتی بیکران هیچ محدودیتی برای تعداد اشیا ندارد؛ یعنی از هر شی، به هر تعداد دلخواهی می‌توان انتخاب کرد. نسخه‌ای از این سؤال که بیش از همه مورد توجه قرار می‌گیرد، دارای ویژگی‌های زیر است:
یک مسئله تصمیم است.
مسئله ۰ و ۱ است.
برای هر شی، وزن و ارزش آن برابرند؛ یعنی w_{i}=v_{i}.
دقت کنید که در این مورد خاص، این مسئله هم ارز است با: " مجموعه‌ای از اعداد صحیح نا منفی داده شده است. آیا زیر مجموعه‌ای از آن وجود دارد که جمع اعضایش دقیقاً  W شود؟" و چنانچه وزن‌های منفی هم قابل قبول باشند، و  W برابر با  0 در نظر گرفته شود، مسئله عبارت است از: " مجموعه‌ای از اعداد صحیح داده شده است. آیا زیر مجموعه‌ای غیر تهی از آن هست که جمع اعضایش  0 شود؟" این مسئله خاص، مسئله جمع زیرمجموعه‌ها نامیده می‌شود. در رمزنگاری، هر گاه از مسئله کوله‌پشتی نام برده می‌شود، منظور مسئله جمع زیرمجموعه‌ها است.
چنانچه چند کوله‌پشتی داشته باشیم، مسئله تبدیل به سؤال bin packing می‌شود.