Учитывая мультимножество натуральных чисел X, рассмотрим множество всех возможных сумм:
Например, а .
Какой алгоритм расчета обратной операции наиболее эффективен (измеряется в терминах размера входного набора сумм)? В частности, возможно ли эффективно рассчитать любое из следующего:
- Является ли данный набор допустимым набором сумм. (Например, является действительным, а - нет.){ 0 , 1 , 3 }
- Мультимножество, которое суммирует данный набор.
- Наименьшее MultiSet , что суммы в данном наборе. (Например, и оба сумму но первое меньше.){ 1 , 1 , 1 } { 0 , 1 , 2 , 3 }
algorithms
optimization
combinatorics
integers
Ури Гранта
источник
источник
Ответы:
Решение
Решение состоит из двух частей. Сначала мы обнаруживаем минимальное множество, а затем доказываем, что оно может представлять множество степенной суммы. Решение адаптировано для реализации программ.
Алгоритм минимального набора
Найдите максимальный элемент из набора сумм (мульти). , потенциальный минимальный (мульти) набор изначально пуст. рam P
Если не существует только одной группы, представляйте всеми возможными способами в виде пары сумм, которые складываются в , a m S i j = { ( a i , a j ) | a i + a j = a m }am am Sij={(ai,aj)|ai+aj=am}
Убедитесь, что все элементы из набора сумм включены.
Найти максимальный элемент из всех (означающего вместе) со следующим свойством: для каждого , является либо в , или мы можем найти из набор сумм, так что находится в . S i j S i j a s S i j a p a p + a s S i jas Sij Sij as Sij ap ap+as Sij
Если это так, тоSij не содержит S , просто сумма сек + а р , удалить р + S из S я J (или просто установить метку , чтобы игнорировать его) и вставить в р и а S в S я J вместо.as as+ap ap+as Sij ap as Sij
Если элемент присутствует в каждом удалить его из всех S я J один раз (или просто установить метку , чтобы игнорировать его и не трогать его больше) и добавить его в список элементов потенциального минимального множества P .Sij Sij P
Повторяйте, пока все не опустеютSij
Если некоторые из остаются непустыми и мы не можем продолжить, попробуйте еще раз с максимальным значением из всех S i j .Sij Sij
Воссоздать рекурсивные шаги без удалений и продолжить с алгоритмом булеан покрытия над . (Перед этим вы можете выполнить безопасную проверку того, что P включает все элементы, которые не могут быть представлены в виде суммы двух элементов, поэтому они обязательно должны быть в базовом наборе. Например, минимальный элемент должен быть в P. )P P P
(10. Обратите внимание, что решение с минимальным множеством, являющееся целью алгоритма, не может содержать более одного повторения одного и того же числа.)
Пример:
Представьте 15 всеми возможными способами как сумму двух чисел из набора сумм.
Попробуйте найти максимальное число, которое есть во всех группах или которое может быть представлено в виде суммы. Очевидно, что мы можем начать поиск с 8, нет смысла идти над ним.
13 из первой группы - 13 = 8 + 5, так что 13 - это хорошо, но 12 из второй группы - не хорошо, поскольку в наборе сумм нет 4, чтобы сделать 12 = 8 + 4. Далее мы попробуем с 7. Но сразу 13 не может быть покрыто, нет 6.
Далее мы попробуем 5. 13 = 5 + 8, 12 = 5 + 7, 10 = 5 + 5, а для последних либо 8 = 5 + 3, либо 7 = 5 + 2, но не оба. Группы сейчас:
5 повторяется во всех группах, поэтому мы извлекаем его . Мы извлекаем 5 только один раз из каждой группы.P={5}
Очевидно, что нет смысла идти выше 5, поэтому мы пробуем 5 снова. 8 = 5 + 3, 7 = 5 + 2, так что все в порядке
Извлеките один 5 снова из всех групп, так как он повторяется. (Это не часто встречается, но наш случай специально создан, чтобы показать, что делать в случае повторения.)P={5,5}
Теперь мы попробуем с 3 и 5 = 3 + 2. Добавьте это в группу.
Теперь извлеките 3 и 2, поскольку они повторяются повсюду, и мы в порядке а группы пусты.P={5,5,3,2}
Теперь нам нужно воссоздать рекурсивные шаги без удалений, это просто означает выполнение вышеописанного без реального удаления элементов из просто поместив их в P и пометив, чтобы они больше не изменялись.Sij P
( ( 5 , 8 ) , 2 ) , ( ( 5 , 7 ) , 3 ) , ( ( 5 , 5 ) , 5 ) , ( ( 5 , 3 ) , 7
Электропитание покрытия
Цель этой части состоит в том, чтобы проверить, может ли найденный минимальный набор покрыть набор суммы мощности. Вполне возможно, что найденное решение может охватывать все заданные суммы, но они не являются установленными суммами. (Технически, вы могли бы просто создать набор суммы мощности из найденного минимального набора и проверить, находится ли каждая сумма, как предписано набором мощности, в начальном наборе суммы. Это все, что просто слилось с тем, что у нас уже есть, поэтому ничего не теряется Вы можете выполнить эту часть, перематывая рекурсию.)
с кодировкой: 2 с 1, 3 с 2, 5 с 4 и еще 5 с 8. Обратите внимание, что каждый элемент имеет различную кодировку, даже если они повторяются.
Если какое-либо двоичное представление соответствует сумме, которую невозможно найти, сообщите, что решения не существует.
обсуждение
Необходимо было предоставить алгоритм, который будет проверять, покрывают ли суммы завершение набора мощности, что скрыто в бинарном расширении. Например, если мы исключим 8 и 7 из исходного примера, первая часть все равно предоставит решение, только вторая часть сообщит о пропущенных комбинациях сумм.
Части алгоритма предполагают, что мы можем найти пару сумм за линейное время, и это требует сортировки.
Неправильный старт
Цель этого алгоритма состоит в том, чтобы обеспечить решение, как только мы все правильно запустили.
улучшения
Шаг 4. это тот, который можно обновить таким образом: вместо максимального мы могли бы попробовать каждый элемент в порядке убывания, который удовлетворяет данному условию. Мы создаем отдельную ветку для каждого. Если какая-то ветка не дает решения, отмените его.
Другое дело, поскольку мы знаем, что у нас не может быть более одного повторения, если случай минимален, мы можем включить это в наш алгоритм.
В целом, условие на шаге 4. что число должно повторяться в каждой группе или иметь возможность создавать сумму, достаточно сильно, чтобы вытащить нас из прямых экспоненциальных вод, что было бы алгоритмом простого опробования каждой комбинации и создания силы установить над каждым, пока мы не найдем совпадение.
источник
ПРИМЕЧАНИЕ. В целом это не совсем работает, см. Контрпример Ури ниже.
источник