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

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

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

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

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

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

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

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

Любая помощь приветствуется. Спасибо!


partition algorithm np complexity-theory
person Free    schedule 01.12.2014    source источник

Ответы (1)


arrow_upward
3
arrow_downward

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

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

person mcdowella    schedule 01.12.2014