Одновременные суммы подмножеств

Question

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

Проблема:

Предположим, у вас есть два списка положительных чисел A1, A2, A3 ... и B1, B2, B3 ... с одинаковым количеством элементов N. Есть две суммы Sa и Sb. Задача состоит в том, чтобы найти одновременное множество Q, где | sum (A {Q}) - Sa | <= эпсилон и | сумма (B {Q}) - Sb | <= эпсилон. Итак, если Q равен {1, 5, 7}, то A1 + A5 + A7 - Sa <= epsilon и B1 + B5 + B7 - Sb <= epsilon. Эпсилон - сколь угодно малая положительная постоянная. </p>

Теперь я мог бы решить это как две совершенно разные задачи о подмножестве сумм, но снятие ограничения одновременности приводит к возможности ошибочных решений (где Qa! = Qb). Я также подозреваю, что дополнительное ограничение должно облегчить эту проблему, чем две проблемы полного NP. Я хотел бы решить экземпляр с 18+ элементами в обоих списках чисел, и большинство алгоритмов подмножества сумм имеют длительное время выполнения с таким количеством элементов. Я исследовал псевдополиномиальный алгоритм динамического программирования во время выполнения, но в этом есть проблемы: а) скорость зависит от небольшой битовой глубины списка чисел (что не обязательно относится к моему экземпляру) и б) он делает не принимать во внимание ограничение одновременности.

Какой-нибудь совет, как использовать ограничение одновременности для сокращения времени выполнения? Есть ли подход динамического программирования, который я мог бы использовать, чтобы учесть это ограничение?

Answer 1

Если я правильно понимаю ваше описание проблемы (меня смущает, почему у вас есть символы расстояния вокруг «сумма (A {Q}) - Sa» и «сумма (B {Q}) - Sb», это кажется, не соответствует остальной части объяснения), тогда это в NP.

Это можно увидеть, уменьшив сумму поднабора (SUB) до суммы одновременного поднабора (SIMSUB). Если у вас есть проблема SUB, состоящая из набора X = {x1, x2, ..., xn} и цели с именем t, и у вас есть алгоритм, который решает SIMSUB, когда заданы два набора A = {a1, a2, ... , an} и B = {b1, b2, ..., bn}, два целых числа Sa и Sb и значение для epsilon, тогда мы можем решить SUB следующим образом: Пусть A = X и B - множество длины n, состоящее только из 0. Установите Sa = t, Sb = 0 и epsilon = 0. Теперь вы можете запустить алгоритм SIMSUB для этой проблемы и получить решение вашей проблемы SUB. Это показывает, что SUBSIM такой же твердый, как SUB, и поэтому в NP.