Рекурсивно разделить список, который каждая итерация делит на две части, чтобы получить ближайшую общую сумму

Дан список чисел L = {a1, a2, a3, a4, ..., aN}

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

(добавлено: 9 июня) Например, если у нас есть L = {10, 20, 1, 2} (отредактировано: 10 июня) решение может быть таким: сначала разделить его на {10, 1, 2} и {20}, затем разделить первое на {1, 2} и {10}, продолжить с {1, 2} до {1}, {2}. Теперь все члены L теперь атомарны и больше не могут быть разделены.

После разделения он должен выглядеть как какое-то бинарное дерево.

Скажем так..

  (a1 a2 a3 a4)
       /\
      /  \
     /    \
    /      \
 (a1 a2) (a3 a4)
   /\      /\
  /  \    /  \
(a1)(a2)(a3)(a4)

В каждом узле функция подобия

abs( sum(left_child) - sum(right_child) ) / sum(itself)

Я хочу найти "оптимизированный" способ разделить список (создать дерево) в соответствии с "суммированием" этой функции. Обратите внимание, что на верхнем уровне это значение может иметь большее влияние, чем на нижнем , поэтому веса должны быть предоставлены.

weight(level) * abs( sum(left_child) - sum(right_child) ) / sum(itself)

пусть level — это уровень этого узла в бинарном дереве.

Я думаю, что это можно решить с помощью динамического программирования с временной сложностью O (2 ^ N). Однако это решение кажется мне слишком медленным. У кого-нибудь есть лучшие решения?

Приветствуются как оптимизация, так и аппроксимация.

Заранее спасибо.


partition-problem algorithm approximation dynamic-programming binary-tree
person Phizaz    schedule 09.06.2015    source источник
comment
проверьте мой ответ, я обновил его, чтобы он подходил для вашего случая проблемы.   -  person Ashkan Kazemi    schedule 09.06.2015
comment
@AshkanKzme Я проверил это, но обнаружил, что это не соответствует моей точке зрения, потому что я хочу минимизировать суммирование функции сходства (упомянутое выше) ... предложенное вами решение будет оптимизировано для каждого узла но не для всего дерева.. кстати. большое спасибо за быстрый ответ   -  person Phizaz    schedule 09.06.2015
comment
@AshkanKzme ты удалил свой ответ? или я опять что-то не так сделал? Я в шоке, когда обновился и ничего не нашел..   -  person Phizaz    schedule 09.06.2015
comment
Я удалил ответ, так как он не дал правильного решения вашей проблемы. и я думаю, что вы не можете получить лучшее время работы O (2 ^ N) с ограничением веса, которое у вас есть, это делает проблему чрезвычайно сложной для решения!   -  person Ashkan Kazemi    schedule 09.06.2015
comment
абсолютно необходимо сделать это рекурсивно? я считаю, что есть много способов получить желаемый результат за время O(n) без использования рекурсии.   -  person Dleep    schedule 09.06.2015
comment
@EmilianoSorbello Я не хочу использовать рекурсию для решения этой проблемы. Я сказал это только для пояснения ... Я думаю, вы можете предложить любой алгоритм, решающий эту проблему.   -  person Phizaz    schedule 10.06.2015

Ответы (1)


arrow_upward
0
arrow_downward

Временная сложность O (n), но действительно неточный подход:

def distance(a, b):
    return abs(a - b)

def balancedSlice(myList):

    total = sum(myList)
    a = 0        #a, b are the sum's of each slice
    b = total
    dist = distance(a, b) # current distance between slices
    for i in range (len(myList)):
        a += myList[i]
        b -= myList[i]
        if dist <= distance(a, b):
            return myList[:i],myList[i:] #list sliced "from 0 to before i" and "from i to end"
        dist = distance(a, b)

Другой, чуть более точный, но не идеальный жадный алгоритм за O(n log n):

def balancedSlice(myList):
    list1 = list()
    list2 = list()
    myList = list(myList) #skip if you can destroy the original list.
    myList.sort() # O(n log n)
    while myList:
        item = myList.pop()
        if sum(list1) <= sum(list2):
            list1.append(item)
        else:
            list2.append(item)
    return list1, list2

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

person Dleep    schedule 10.06.2015
comment
Я понял вас сейчас.. дело в том, что порядок элементов в списке не важен.. Я могу их перетасовать и должен получить тот же результат. Еще одна вещь ... вы также должны гарантировать, что общее расстояние будет сведено к минимуму в соответствии с функцией, которую я дал ... извините за мое плохое объяснение. - person Phizaz; 10.06.2015
comment
Итак, у вас есть куча предметов, и вы хотите упаковать их в 2 пакета (списки, наборы и т. д.), чтобы они были как можно более сбалансированными, верно? - person Dleep; 10.06.2015
comment
не просто 2 сумки, потому что каждая сумка может иметь свои собственные подмешки, см. бинарное дерево выше: D - person Phizaz; 10.06.2015