Разделить подмножество с ограничением

Сегодня, практикуя некоторые вопросы Алгоритма, я нашел интересный вопрос. Вопрос в том

Вы должны разделить 1 на n (с одним пропущенным значением x) на две равные половины, так что сумма двух половин равна.

Пример:

Если n = 7 а также x = 4

Решение будет {7, 5} а также {1, 2, 3, 6}

Я могу ответить на него методом грубой силы, но я хочу эффективное решение Может кто-нибудь помочь мне?

Источник

2 ответа

Если сумма элементов 1→N без x нечетна, то решения не существует.

В противном случае вы можете найти свое решение в O(N) со сбалансированным выбором.

4 в ряд

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

[x, x +1, x + 2, x + 3] → [x + 3, x]; [x + 2, x +1]

Таким образом, выбирая их и помещая их в наборы A B B A, балансные наборы A и B.

4 поперек

Более того, когда у нас есть две пары в пропущенном значении, оно может содержать похожее свойство:

[x-2, x-1, x +1, x + 2] → [x + 2, x-2]; [х +1, х-1]

так до сих пор A B B A

На данный момент мы можем исправить следующие случаи:

  • у нас есть четверка: мы разбиваем ее, как в случае 1
  • у нас есть 2 числа, х и другие 2 числа: мы разделяем, как в случае 2

Хорошо, но это может случиться, у нас есть 3 числа, х и другие 3 числа, или другие условия. Как мы можем выбрать сбалансированный способ в любом случае?

+2 разрыв

Если мы снова посмотрим на разрыв через х:

[х-1, х +1]

мы можем заметить, что каким-то образом, если мы разделим двух соседей на два отдельных набора, мы должны сбалансировать +2 на множестве с большей суммой.

Балансирующий Хвост

Мы можем сделать это, используя последние четыре числа последовательности:

[4 3 2 1] → [4, 2]; [3, 1] → 6; 4

Наконец, мы должны учитывать, что у нас может не быть одного из них, поэтому давайте создадим другой случай:

[3 2 1] → [2]; [3, 1] → 2; 4

и давайте также поймем, что мы можем сделать то же самое на другом конце последовательности с шаблоном A B A B (или B A B A) - если наш +2 стоит на B (или A);

4 поперек +

Удивительно, что 4 по-прежнему сохраняется, если мы прыгаем h (нечетное!) Число

[x+3, x+2, x-2, x-3] → [x+3, x-3]; [х + 2, х-2]

Итак, исследуя массив, мы можем нарисовать решение шаг за шагом

Пример:

11 10 9 8 7 6 5 4 3 2 1

сумма четная, поэтому x может быть только четным числом:

x = 10
11 - 9 | 8 7 6 5 | 4 3 2 1 → (+2 gap - on A) (4 in a row) (balancing tail)
 A   B   A B B A   B A B A

x = 8
11 10 | 9 - 7 | 6 5 | 4 3 2 1 → (4 across +) (+2 gap - on A) (balancing tail)
 a  b   A   B | b a | B A B A

x = 6
11 10 9 8 | 7 - 5 | 4 3 2 1 → (4 in a row) (+2 gap - on A) (balancing tail)
 A  B B A   A   B   A B B B

x = 4 we have no balancing tail - we have to do that with head
11 10 9 8 | 7 6 | 5 - 3 | 2 1 → (balancing head) (4 across +) (+2 gap)
 A  B A B   A B | b   a | B A

x = 2
11 10 9 8 | 7 6 5 4 | 3 - 1 → (balancing head) (4 in a row) (+2 gap)
 A  B A B   A B B A   B   A

Интересно отметить симметрию решений. Другой пример.

10 9 8 7 6 5 4 3 2 1

сумма нечетная, поэтому x может быть только нечетным числом, а количество элементов теперь нечетным.

x = 9
10 - 8 | 7 6 5 4 | 3 2 1 → (+2 gap - on A) (4 in a row) (balancing tail)
 A   B   A B B A   B A B

x = 7
10 9 | 8 - 6 | 5 4 | 3 2 1 → (4 across +) (+2 gap - on A) (balancing tail)
 a b | A   B | b a   B A B

x = 5
10 9 8 7 | 6 - 4 | 3 2 1 → (4 in a row) (+2 gap - on A) (balancing tail)
 A B B A   A   B   B A B

x = 3
10 9 8 7 | 6 5 | 4 - 2 | 1 → (balancing head) (4 across + virtual 0) (+2 gap)
 A B A B   B A | a   b | A

x = 1
10 9 8 7 | 6 5 4 3 | 2 → (balancing head) (4 in a row) (+2 gap virtual 0)
 A B A B   A B B A   B

Наконец, стоит отметить, что мы можем переключаться с A на B всякий раз, когда у нас есть полностью сбалансированный сегмент (то есть 4 подряд или 4 поперек)

Смешно сказал - но свойство, запрашивающее сумму ([1 ... N]-x), даже делает дела весьма излишними, если вы попробуете сами.

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

Источник

Эту проблему можно решить, обернув стандартную задачу подмножества динамического программирования в этапы предварительной обработки. Эти шаги O(1) ком

Алгоритм (n, x):

  1. сумма = n * (n+1) / 2
  2. Необходимая сумма = сумма - х

  3. If (requiredSum % 2!= 0): вернуть 0

  4. создать массив [1..n] и удалить из него x

  5. вызвать стандартную подмножество (arr, 0, requiredSum/2, [])

Реализация алгоритма подмножества в Python - печать всех подмножеств приведена ниже.

def subsetsum(arr, i, sum, ss):
    if i >= len(arr):
        if sum == 0:
            print ss
            return 1
        else:
            return 0

    ss1 = ss[:]
    count = subsetsum(arr, i + 1, sum, ss1)
    ss1.append(arr[i])
    count += subsetsum(arr, i + 1, sum - arr[i], ss1)
    return count


arr = [1, 2, 3, 10, 5, 7]
sum = 14
a = []
print subsetsum(arr, 0, sum, a)

Надеюсь, поможет!

Источник
Другие вопросы по тегам