Описание тега knapsack-problem
Проблема рюкзака - это проблема комбинаторной оптимизации: по заданному набору элементов с соответствующими весами и значениями определить количество каждого элемента, которое нужно включить в коллекцию, чтобы общий вес был меньше или равен заданному пределу и максимизировал Общая стоимость. Это NP-полная проблема, но несколько общих упрощений эффективно решаются с помощью динамического программирования.
Существует несколько вариантов задачи о ранце, например задача о ранце 0-1, ограниченная и неограниченная задача о ранце. Неограниченный рюкзак и рюкзак 0-1 эффективно решаются с помощью техники " разделяй и властвуй" (динамическое программирование).
Другие варианты, где можно взять нецелое количество предмета, веса являются действительными числами (и случаи, когда другие ограничения становятся действительными вместо целых), являются NP-полными.
Проблема с несколькими рюкзаками часто упоминается как проблема упаковки в бункеры.