Доброго!

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

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

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

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

Здравствуйте, xy012111, Вы писали:

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


Вот на примерку подборка рюкзачков: вики

Здравствуйте, andy1618, Вы писали:

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

A>Вот на примерку подборка рюкзачков: вики

Спасибо, узнал, что задача распространённая и по каконическому названию Multiple knapsack problem нашёл http://www.or.deis.unibo.it/knapsack.html там глава шестая даже с псевдокодом. Если руки доберутся сделать правильно, то отпишусь что вышло.