Эта проблема, по сути, является обобщением проблемы суммы подмножеств (которая является NP-полной, да) для нескольких измерений. Чтобы переформулировать проблему (чтобы убедиться, что мы решаем ту же проблему): у вас есть 1000 предметов, разделенных на 20 классов (которые вы называете слоты). Каждый элемент имеет целочисленное значение в [-10,10] для каждого из 8 свойств; таким образом, каждый элемент может рассматриваться как имеющий значение, которое является 8-мерным вектором. Вы хотите выбрать один элемент из каждого слота, чтобы общее значение (с добавлением этих 8-мерных векторов) было заданным вектором.
В приведенном вами примере у вас есть 4 измерения, а 9 элементов в 3 классах имеют значения (2,0,2,1), (5,0,1, -1), ... и т. Д., И вы хочу выбрать один предмет из каждого класса, чтобы составить сумму (3,3,8,0). Правильно?
перебор
Во-первых, это перебор, который перечисляет все возможности. Предполагая, что ваши 1000 предметов разделены поровну на 20 классов (то есть, у вас есть 50 в каждом), у вас есть 50 вариантов для каждого класса, что означает, что вам нужно проверить 50 20 = 9536743164062500000000000000000000 вариантов (и для к каждому из них нужно сложить 20 элементов вдоль каждой из 8 координат и проверить, чтобы время выполнения составило ∝ 50 20 & middot; 20 & middot; 8): это неосуществимо.
Динамическое программирование, одиночный выстрел
Тогда есть решение для динамического программирования, которое отличается и на практике часто работает там, где грубая сила невозможна, но в этом случае, к сожалению, также кажется невозможной. (Вы бы улучшили его в геометрической прогрессии, если бы получили более точные границы для своих «значений свойств».) Идея здесь состоит в том, чтобы отслеживать один из способов достижения каждого возможного sum . Сумма из 20 чисел из [-10,10] лежит в [-200,200], поэтому для вашего 8-мерного вектора есть «только» 400 8 = 655360000000000000000 возможных сумм. (Это небольшая часть другого пространства поиска, но это вас не утешает. Для каждого «свойства» вы также можете взять разницу между суммами [самый большой элемент в каждом классе] и [наименьший элемент в каждом классе ] заменить 400 на меньшее число.) Идея алгоритма динамического программирования заключается в следующем.
Пусть last [(a, b, c, d, e, f, g, h)] [k] обозначает один предмет, который можно взять из k-го класса (вместе с одним предметом из первого k -1 классы), чтобы сделать сумму точно (a, b, c, d, e, f, g, h).
Тогда псевдокод:
for k=1 to 20:
for each item i in class k:
for each vector v for which last[v][k-1] is not null:
last[v + value(i)][k] = i
Затем, если желаемая конечная сумма равна s, вы выбираете элемент last [s] [k] из k-го класса, элемент last [s-value (i)] [k-1] из (k-1) й класс и тд. В худшем случае это занимает время & 20 - середина; 50 - середина; 400 8 - середина 8 (только свободная верхняя граница, а не жесткий анализ).
Динамическое программирование, отдельно
Так много для "идеальных" решений. Однако, если вы разрешите эвристические решения и те, которые «скорее всего, будут работать на практике», вы можете добиться большего успеха (даже для точного решения проблемы). Например, вы можете решить проблему отдельно для каждого из 8 измерений. Это еще проще реализовать, и в худшем случае это займет всего лишь время ∝ 20 & middot; 50 & middot; 400 & middot; 8 = 3200000, и вы можете сделать это довольно легко. Если вы сохраните последний [] [] как список, а не как отдельный элемент, то в конце вы получите (эффективно) список подмножеств, которые достигают заданной суммы для этой координаты (в форме продукта) «). На практике, не так много подмножеств могут составить именно ту сумму, которую вы хотите, поэтому вы можете начать с координаты, для которой количество подмножеств наименьшее, а затем попробовать каждое из этих подмножеств для остальных 7 координат. Сложность этого шага зависит от данных в задаче, но я подозреваю (или можно надеяться), что либо (1) будет очень мало наборов с равными суммами, и в этом случае это пересечение сократит количество наборов до проверьте, или (2) будет много наборов с заданной суммой, и в этом случае вы найдете один довольно рано.
Вв любом случае, выполнение динамического программирования отдельно для каждой координаты в первую очередь определенно позволит вам выполнять поиск в гораздо меньшем пространстве на втором этапе.
Приближенные алгоритмы
Если вам не нужны суммы, равные точно , и вы будете принимать суммы, которые находятся в пределах определенного фактора от вашей требуемой суммы, есть известная идея, используемая для получения FPTAS (полностью схема аппроксимации полиномиального времени) для задачи о сумме подмножеств, которая выполняется во временном полиноме по (количеству элементов и т. д.) и 1 / ε. Я исчерпал свое время, чтобы объяснить это, но вы можете посмотреть его - в основном, он просто заменяет пространство 400 8 на меньшее, например, округление чисел до ближайшего кратного 5 или любого другого значения.