Доброго!

Имеется задача, очень похожая на задачу о рюкзаке, но с небольшими разницами, главная из которых заключается в том, что рюкзаков имеется несколько штук и вместимость у каждого своя.

На первых порах достаточно приближённого решения.

Хочу применить что-то вроде жадного алгоритма для такого случая (имеющегося не нашёл, буду благодарен на ссылки на подобные задачи). То есть, отсортировав предметы по убыванию удельной стоимости, сортирую так же и рюкзаки по убыванию вместительности и заполняю рюкзаки по очереди от большего к меньшему обычным жадным алгоритмом. Можно ли тут что-то улучшить? Например, не будет ли выгоднее заполнять рюкзаки не по очереди, а одновременно (первый предмет с наибольшим удельным весом в самый вместительный рюкзак, предмет со вторым по величине удельным весом — во второй рюкзак и т.д.)?

Другая разница (это уже следующий этап, предыдущий вопрос интересен и без этого) моей задачи по сравнению с классической в том, что для каждого предмета имеется большой ряд аналогичных же предметов, но другого веса, причём величина веса может "гулять" в довольно широких (в разы) пределах, но снижая при этом ценность. Может быть так, что количество аналогов сопоставимо с количеством имеющихся предметов без учёта аналогов. А цель задачи — взять как можно больше [различных] предметов и что бы стоимость взятого была бы как можно выше :о)) В какую сторону посоветуете копать здесь?