Модификация метода Лагариаса–Одлыжко для решения обобщённой задачи о рюкзаке и систем задач о рюкзаках

В работе 1985 г. Дж. Лагариас и А. Одлыжко предложили метод решения вычислительной задачи о рюкзаке, основанный на её сведении к задаче поиска короткого вектора в решётке специального вида. Метод Лагариаса–Одлыжко позволяет решать “практически все” задачи о рюкзаках, обладающие малой плотностью. В настоящей работе метод Лагариаса–Одлыжко решения задачи о рюкзаке модифицируется применительно к случаям обобщённой задачи о рюкзаке и систем задач о рюкзаках. Система задач о рюкзаках вводится в настоящей работе как конечное множество индивидуальных задач о рюкзаках, имеющих общее решение. Определяются множества значений плотности обобщённых задач о рюкзаках и систем задач о рюкзаках, такие, что модифицированные методы позволяют решать “практически все” обобщённые задачи о рюкзаках и системы задач о рюкзаках, обладающие плотностью из этих множеств.