Ниже алгоритм точного решения целочисленной задачи о рюкзаке. Предлагаемый алгоритм требует меньше вычислительных ресурсов и возможно проще алгоритма динамического программирования (ДП).

Причина побудившая автора к публикации

Описание алгоритма было послано мною в институт математики им. С. Л. Соболева Сибирского отделения РАН, откуда был прислан ответ что указанный алгоритм известен давно. Цитирую:

Одно из его первых упоминаний в книге Кереллера Nemhauser, Ullman, Discrete dynamic programming and capital allocation, Management Science, 15 p. 494-505, 1969.

Риторический вопрос почему в учебниках по дискретной математике этого алгоритма нет, остался без ответа. Обоснование того, что алгоритм не является полиномиальным я не понял. До алгоритма я дошел самостоятельно, так что надеюсь ничьих прав не нарушаю. Возможно кому нибудь описание будет интересно и пригодится.
Читать дальше →