Для решения задачи о рюкзаке используются различные алгоритмы, среди них:

• Полный перебор. 4 Задача решается путём перебора всех возможных решений. 4 Для каждого предмета существует два варианта: он кладётся в рюкзак или нет. 4
• Жадный алгоритм. 4 Вещи сортируются по их удельной ценности (отношению ценности предмета к его весу), и в рюкзак помещаются предметы с наибольшей удельной ценностью. 4
• Метод ветвей и границ. 24 Сводится к построению дерева возможных вариантов, определению оценки границы решения для каждой вершины дерева, отсечению бесперспективных вершин. 2
• Метод динамического программирования. 13 Задача разбивается на набор простых подзадач, для которых составляется таблица с оптимальными решениями. 13 Программа рассматривает варианты решения и выбирает лучший. 3
• Метод отсечения. 2 Идея метода в снятии условия целочисленности и поиске оптимального решения двойственным симплекс-методом. 2

Задача о рюкзаке относится к классу NP-полных, поэтому при её решении приходится выбирать между точными алгоритмами, которые неприменимы для «больших» рюкзаков, и приближёнными, которые работают быстро, но не гарантируют оптимального решения. 4