1

给定一个数字列表 L = { a1, a2, a3, a4, ... , aN}

问题是将这个L分成两部分，不仅仅是一次，而是递归的，直到它变成原子的。主要思想就像这篇文章，但添加了递归的东西。

（添加：6 月 9 日） 例如，如果我们有 L = {10, 20, 1, 2} （编辑：6 月 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)

let level是该节点在二叉树中的级别。

我认为可以使用时间复杂度为 O(2^N) 的动态编程来解决这个问题。但是，这个解决方案对我来说似乎太慢了。有人有更好的解决方案吗？

也欢迎优化和近似。

先感谢您。

4

1 回答 1

0

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 问题，所以如果你的列表足够大并且你可以容忍不完美的结果，你应该坚持使用这种贪心算法。

于 2015-06-10T01:47:22.150 回答