Какое правильное название проблемы / алгоритм для этого описания проблемы в теории информатики?

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

Это напомнило мне о «ранце», но у меня есть несколько ранцев разных размеров, и все они должны быть относительно эквивалентными (например, один рюкзак может вмещать только 12 фунтов, а другой - только 8 фунтов, но оба они должны быть заполнены одинаковым процентом от общего веса, который они могут нести). Это также напоминает мне "упаковку мусора". проблема, но это не касается меняющихся размеров бункеров или того, что бункеры не нужно заполнять или сворачивать, им просто нужны эквивалентные нагрузки, и все они должны использоваться.

Кто-нибудь, пожалуйста, укажите мне правильное направление названия этой проблемы в рамках структур данных и теории алгоритмов? Мне также были бы интересны любые алгоритмы или эвристики, которые могут обычно использоваться для решения подобной проблемы, или информация о возможной временной сложности.

13
задан aoeu 12 December 2010 в 03:25
поделиться