Разбивает массив на две части с равными суммами P или NP?

Question

Это был вопрос интервью алгоритма о проблеме разбиения.

Вам дан массив, который состоит чисел от 0 до 5 цифр. Напишите функцию, которая будет возвращать, можно ли разделить массив на 2 половины такой, что сумма две половинки были бы равны.

Это проблема NP или ее можно решить с помощью динамического программирования?

"от 0 до 5 цифр", я думаю, 0 ~ 99999.

---

Я нашел хороший ответ на это за пределами SO здесь .

Answer 1

Это явно NP - решение можно проверить за полиномиальное время.

Однако он не является NP-полным, поскольку элементы ограничены ( число в диапазоне от 0 до 5 цифр ).

Известно, что эта проблема претерпевает "фазовый переход": она легка для m / n <1 и тяжела в противном случае </p>

Answer 2

Вопросы для интервью предназначены не только для проверки решения проблем, но и для анализа проблем. Поэтому эта проблема недостаточно конкретна.

Могу ли я выбрать любые два подмножества элементов или, возможно, они должны быть последовательными частями? В первом случае проблема является NP-Complete (подробнее см. http://en.wikipedia.org/wiki/Partition_problem), во втором она, конечно, тривиальна (вопросы интервью часто заканчиваются тривиальными задачами программирования).

Если основная проблема - NP-Complete, может быть, мы можем попытаться специализировать ее? Что мы знаем о массиве? Может быть, мы можем упростить задачу, сделав некоторые внешние предположения?

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

Обновление: для заданного диапазона чисел проблема эквивалентна дискретной задаче о ранце (с размером ранца, ограниченным половиной суммы всего массива и набором весов размера 100000, это означает, что мы можем решить ее в Вовремя) См. http://en.wikipedia.org/wiki/Knapsack_problem для получения дополнительной информации о проблеме ранца.

Answer 3

Оба.Проблема в NP, и я почти уверен, что она может быть решена за псевдополиномиальное время с помощью динамического программирования.

http://en.wikipedia.org/wiki/Partition_problem

Общая проблема является NP-полной и можетрешаться в псевдополиномиальное время с помощью динамического программирования.T

Это конкретное ограничение чисел от 0 до 5, вероятно, не является NP-полным.В любом случае, что такое 0-значный номер?

Обычно для проблемы с разделами не требуется, чтобы разделы были одинакового размера, просто они имеют одинаковую сумму.Но здесь вы говорите «разделить на 2 половины», я не уверен, что «половина» означает половину массива или просто половину общего.

Я предполагаю, что эта разница,если это разница, вероятно, не влияет на сложность решения DP, но я не уверен.У меня нет никаких доказательств, кроме как: «Эм, да, похоже, что вы можете делать с DP, я бы подумал об этом».

Answer 4

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

Линейный алгоритм для решения подмножества суммы NP-Complete. Чистая реализация Python

https://github.com/maxtuno/Universal/blob/master/linear_sum_subset_algorithm_oscar_riveros.py

#!/usr/bin/env python3

__author__ = "O. A. Riveros"
__copyright__ = "Copyright 2014, O. A. Riveros, All right reserved"
__license__ = "MIT"
__email__ = "oscar.riveros@gmail.com"

"""
O. A. Riveros
http://independent.academia.edu/oarr
http://twitter.com/maxtuno
"""

"""
first 100 primes
"""
data = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541]

solution = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]

"""
for custom entertainment
solution = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
"""

target = sum([data[i] for i in range(len(solution)) if solution[i] == 1])

l = len(data)

size = len('{0:b}'.format(sum(data)))

def rotate(l,n):
    return l[n:] + l[:n]

def slice(l, n):
    return list(int(l[i:i+n], 2) for i in range(0, len(l), n))

data_second_order = []
for i in range(l):
    data_second_order += rotate(data, i)

T = 0
for i in range(l):
    T += int(''.join('{0:b}'.format(k).zfill(size) for k in rotate(data_second_order, i)), 2)
    t = slice('{0:b}'.format(T).zfill(size*(l**2)), size)
    if (target in t):
        '''
        for review the results
        print('The target {} found in {} steps from {}.'.format(target, i + 1, t))
        '''
        print('The target {} found in {} steps'.format(target, i + 1))
        break

"""
The target 24133 found in 100 steps
"""

Answer 5

Правильно, если числа набора ограничены, тогда проблема получает полиномиальную сложность.

Вы можете использовать методы поиска в бин.

Прочитайте вики-страницу для Partition_Problem, а затемв начале вы найдете ссылку на Subset_Sum_Problem, которая почти эквивалентна.На этой вики-странице вы также найдете полезное чтение