Метод решения задачи о рюкзаке с дополнительным ограничением на число типов предметов

Рассматривается задача формирования рюкзака с максимальной стоимостью при заданном ограничении на число типов предметов в нём. Выбор типов производится из конечного множества, количество предметов каждого типа неограниченно. При учёте дополнительного ограничения на число типов предметов в рюкзаке (не более $d^*$ из $n$ возможных типов) известные методы решения задачи о рюкзаке малоэффективны. Предлагаемый в статье метод опирается на идею динамического программирования вычислений с использованием результатов предыдущих шагов. На первом шаге алгоритма определяется максимальная стоимость формируемых виртуальных рюкзаков при их заполнении предметами только одного типа. На втором и последующих шагах определяется максимальная стоимость виртуальных рюкзаков при их последовательном заполнении предметами двух типов, на третьем — трёх типов и т. д. При вычислениях текущего максимального наполнения виртуальных рюкзаков используются результаты, полученные на предыдущем и первом шагах. Доказывается, что предложенный метод позволяет получать глобальный экстремум целевой функции и имеет меньшую трудоёмкость по сравнению с известными точными алгоритмами. Приводится оценка вычислительной сложности алгоритма.