Полиномиальный алгоритм времени для заданного разбиения на степени 2?

Question

Это гораздо более сложный вопрос, чем программирование/реализация, поэтому извиняйтесь, если StackOverflow не подходит для него.

Что касается проблемы:

Предположим, что у нас есть набор чисел, и каждое число должно быть положительным целым числом и мощностью 2. Так, например, может быть, у нас есть {1, 1, 2, 4, 8, 8, 8, 8, 128}. Мы хотим разбить это число на A и B, где каждый элемент должен быть точно равен A или B, так что сумма элементов A равна сумме элементов B. Существует ли полиномиальный алгоритм времени для этой ситуации, которая будет всегда либо

• определить, что нет даже раскола не может существовать, или
• возвращения разбиения на A и B таким образом, что их суммы равны?

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

Я знаю, что есть несколько проблем, которые могли бы помочь, и для контекста, я суммировать их здесь:

1. Set-раздел NP-трудной. В set-partition у вас есть набор произвольных чисел. Решение представляет собой разбиение A и B, где каждый элемент находится в точках A или B, таких как sum(A) = sum(B).
2. Подмножество-сумма NP-жесткая. В подмножестве суммы вы имеете набор произвольных чисел. Решение является подмножеством этого множества, так что сумма элементов подмножества равна некоторому требуемому числу, х.

Любая помощь очень ценится. Благодаря!

Answer 1

Один из способов взглянуть на это - сказать, что вы пытаетесь выразить номер цели, который является итогом/2, как сумма предоставленных чисел. Это действительно проблема изменения.

Вот полезная лемма: если у вас есть коллекция монет, значения которых являются значениями двух значений < = 2^k, то вы можете сделать ровно 2^k, или вы не можете сделать любое число большим, или больше, чем 2^k. Чтобы увидеть это, возьмите все свои монеты и, если у вас есть более одной монеты той же ценности, вставьте эти две монеты вместе, чтобы сделать монету следующего максимального значения, пока вы не закончите монету или не достигнете 2^k. Если вы достигнете 2^k, вы закончили. Если вы закончите, у вас есть коллекция одиночных монет с различными значениями, которые по-прежнему равны двум, все меньше 2^k и только одному на разное значение, поэтому результат не может быть добавлен к более чем 2^k -1.

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

Если вы достигли целевого значения, проблема решена. Если нет, вы пропустили правильный ответ? Вы начали с самых больших монет. Ищите свою первую ошибку - вы взяли монету размером 2^k, и есть какой-то способ составить оставшуюся сумму, которая не включает эту монету размером 2^k. Но этот волшебный путь - это способ внести изменения более 2^k, используя монеты стоимостью не более 2^k.Итак, где-то в этом правильном ответе есть набор монет, который добавляет ровно 2^k. Возьмите этот правильный ответ и удалите монеты, которые добавляют до 2^k, и замените его монетой на 2^k, которую вы использовали, и вы получите еще один правильный ответ - так что вы были в конце концов, и если вы можете получить любое решение, вы можете получить его путем многократного использования самой крупной монеты (числа), доступной меньше расстояния до целевого значения.

Проверка соответствия - посмотрите на сокращение суммы подмножества, указанную в http://cs.mcgill.ca/~lyepre/pdf/assignment2-solutions/subsetSumNPCompleteness.pdf, и обратите внимание, что для этого требуются номера, которые не являются точными степенями двух, поэтому я предлагаю здесь, что доказано, что работает только тогда, когда числа являются степенями двух , не претендует на решение NP-полной задачи в полиномиальное время.