平衡分支算法
Balanced Branching Algorithm
所以我正在做一个看起来像这样的学校任务
而且我完全不知道从哪里开始。有人能指出我正确的方向吗？
我的想法是首先计算根节点的差异值（给定的叶值之和的绝对值），然后（以某种方式）检查是否存在高于根值，如果不是，则根值是输入的最小可能差异。我在正确的轨道上吗？目前我似乎无法比这更进一步。
Important note: The tree that is built must "respect" the given order
of the values. For instance if the input is (5, 0, 0, -5) you are not
allowed to build your tree by first combining the first and the last
items into a tree. More formally: at every internal node, the input
values appearing as leaves in the left subtree of that node must all
come before the input values appearing as leaves in the right subtree.
谢谢！
首先，请注意这是一个方便的递归问题：每当合并相邻节点时，都会将问题减少一个节点。问题状态可以完全表示为值列表和最大值；您给定的问题可以作为
发送到解决方案函数中
a = [-1, -5, 4, -2]
balance(a, max(max(a), abs(min(a))))
更简单地说，
balance(a, 5)
此题的右手解法如下：
[-1, -5, 4, -2], 5
[-1, -1, -2], 5 * see note below
[-1, -3], 5
[-4], 5
- 从这里开始，加入是无关紧要的，因为没有剩余的路径可能超过原始差异 5。
我建议采用半贪婪的方法：目标是从最大节点向外工作，避免使情况变得更糟，或者将损害降至最低。
定位最大节点。还要对序列求和：我们不需要浪费任何时间来避免不可避免的求和。例如，给定
-5 1 1 -5 1 1 -5 1
我们不需要 运行 为低于 -5 的想法而尖叫：总数是 -10，所以我们无法避免如此高的差异。这个可能是后期微调的考虑
首先，查看最大节点的每一侧；将每个视为从该节点旁边开始的子列表。搜索和为相反符号的子序列；如果找到了，将其折叠（将该序列作为子问题），然后将其合并到问题节点。
例如：
4 -5 1 1 2 -1 -1 -6 -2 -1 2 -3 2 2
差异是 6，接近中间。将该点的序列分成两个后退子序列，它们的和 运行ning 和：
seq: -1 -1 2 1 1 -5 4
sum: -1 -2 0 1 ...
seq: -2 -1 2 -3 2 2
sum: -3 -3 -1 -4 -2 0
左边（倒转，从-6元素开始的顺序）在第四个元素处达到了平衡和（相反的符号，所以合并它们会减少差异）：-1 -1 2 1是具有正和的最短子序列。将 [1 2 -1 -1], 6 作为子问题（要考虑的子树）重复出现。这将 return 一个子树，例如 ((1 (2 -1) )-1)，值为 1。值列表现在是：
4 -5 1 1 -6 -2 -1 2 -3 2 2
^ this is the sub-tree we just reduced.
现在我们有一个与最大差异相邻的平衡值；这表明下一个操作是合并这两个值：
4 -5 1 -5 -2 -1 2 -3 2 2
从这里类似地继续。请注意，回归到 6 值的自由度在某些情况下可以加快解决方案搜索。
继续分段，我们将把它折叠成
-1 -4 -2 -1 2 -3 2 2
这将从右边开始，逐渐减少...
-1 -4 -2 -1 2 -3 2 2
-1 -4 -2 -1 2 -1 2
-1 -4 -2 1 -1 2
-1 -4 -1 -1 2
-1 -4 -1 1
-1 -4 0
到这里，我们终于爬回了完整列表中最大的剩余值...
-1 -4 0
-1 -4
-5
这足以让你动起来吗？
对于给定的集合a[1]...a[n]，每个对应一个叶节点，很明显每棵树的差异下界为：
B(x[]) = max (abs(x[1]),...,abs(x[n]), abs(sum))
其中sum，所有x[i]的总和，对应于从x[i]构建的每棵树的根节点的权重。
这里的目标只是为了表明总是可以构建一棵树，其差异等于此下限。
分两步实现。
第一步，如果两个相邻节点的符号不同，我们简单地合并它们。这对应于用一个新节点替换这两个节点，其权重是两个权重的总和。该权重的绝对值小于两个输入权重的绝对值的最大值，因此小于边界。我们重复这个过程，直到我们只得到节点（一个新的集合），这些节点的权重都具有相同的符号。
在第二步中，我们必须管理一个从初始权重派生的集合，其中所有权重都具有相同的符号。从它可以创建的所有树的最大节点对应于最上面的那个节点，其权重等于当前活动节点的所有权重之和，即等于初始集合的总和。此总和对应于小于或等于下限的值。
最后得到一棵树，其权值均小于或等于下界。
示例：
-1 -5 4 -2 -> merge -5 and 4
-1 -1 -2 -> all signs equal, 2nd step: the maximum node of this sub-array correspond to the sum -4
有趣的是，我们通过以不同的顺序应用规则获得了相同的结果：
-1 -5 4 -2 -> merge 4 and -2
-1 -5 2 -> merge -5 and 2
-1 -3 -> all signs equal, 2nd step: sum equals -4
所以我正在做一个看起来像这样的学校任务
而且我完全不知道从哪里开始。有人能指出我正确的方向吗？
我的想法是首先计算根节点的差异值（给定的叶值之和的绝对值），然后（以某种方式）检查是否存在高于根值，如果不是，则根值是输入的最小可能差异。我在正确的轨道上吗？目前我似乎无法比这更进一步。
Important note: The tree that is built must "respect" the given order of the values. For instance if the input is (5, 0, 0, -5) you are not allowed to build your tree by first combining the first and the last items into a tree. More formally: at every internal node, the input values appearing as leaves in the left subtree of that node must all come before the input values appearing as leaves in the right subtree.
谢谢！
首先，请注意这是一个方便的递归问题：每当合并相邻节点时，都会将问题减少一个节点。问题状态可以完全表示为值列表和最大值；您给定的问题可以作为
发送到解决方案函数中a = [-1, -5, 4, -2]
balance(a, max(max(a), abs(min(a))))
更简单地说，
balance(a, 5)
此题的右手解法如下：
[-1, -5, 4, -2], 5
[-1, -1, -2], 5 * see note below
[-1, -3], 5
[-4], 5
- 从这里开始，加入是无关紧要的，因为没有剩余的路径可能超过原始差异 5。
我建议采用半贪婪的方法：目标是从最大节点向外工作，避免使情况变得更糟，或者将损害降至最低。 定位最大节点。还要对序列求和：我们不需要浪费任何时间来避免不可避免的求和。例如，给定
-5 1 1 -5 1 1 -5 1
我们不需要 运行 为低于 -5 的想法而尖叫：总数是 -10，所以我们无法避免如此高的差异。这个可能是后期微调的考虑
首先，查看最大节点的每一侧；将每个视为从该节点旁边开始的子列表。搜索和为相反符号的子序列；如果找到了，将其折叠（将该序列作为子问题），然后将其合并到问题节点。
例如：
4 -5 1 1 2 -1 -1 -6 -2 -1 2 -3 2 2
差异是 6，接近中间。将该点的序列分成两个后退子序列，它们的和 运行ning 和：
seq: -1 -1 2 1 1 -5 4
sum: -1 -2 0 1 ...
seq: -2 -1 2 -3 2 2
sum: -3 -3 -1 -4 -2 0
左边（倒转，从-6元素开始的顺序）在第四个元素处达到了平衡和（相反的符号，所以合并它们会减少差异）：-1 -1 2 1是具有正和的最短子序列。将 [1 2 -1 -1], 6 作为子问题（要考虑的子树）重复出现。这将 return 一个子树，例如 ((1 (2 -1) )-1)，值为 1。值列表现在是：
4 -5 1 1 -6 -2 -1 2 -3 2 2
^ this is the sub-tree we just reduced.
现在我们有一个与最大差异相邻的平衡值；这表明下一个操作是合并这两个值：
4 -5 1 -5 -2 -1 2 -3 2 2
从这里类似地继续。请注意，回归到 6 值的自由度在某些情况下可以加快解决方案搜索。
继续分段，我们将把它折叠成
-1 -4 -2 -1 2 -3 2 2
这将从右边开始，逐渐减少...
-1 -4 -2 -1 2 -3 2 2
-1 -4 -2 -1 2 -1 2
-1 -4 -2 1 -1 2
-1 -4 -1 -1 2
-1 -4 -1 1
-1 -4 0
到这里，我们终于爬回了完整列表中最大的剩余值...
-1 -4 0
-1 -4
-5
这足以让你动起来吗？
对于给定的集合a[1]...a[n]，每个对应一个叶节点，很明显每棵树的差异下界为：
B(x[]) = max (abs(x[1]),...,abs(x[n]), abs(sum))
其中sum，所有x[i]的总和，对应于从x[i]构建的每棵树的根节点的权重。
这里的目标只是为了表明总是可以构建一棵树，其差异等于此下限。
分两步实现。
第一步，如果两个相邻节点的符号不同，我们简单地合并它们。这对应于用一个新节点替换这两个节点，其权重是两个权重的总和。该权重的绝对值小于两个输入权重的绝对值的最大值，因此小于边界。我们重复这个过程，直到我们只得到节点（一个新的集合），这些节点的权重都具有相同的符号。
在第二步中，我们必须管理一个从初始权重派生的集合，其中所有权重都具有相同的符号。从它可以创建的所有树的最大节点对应于最上面的那个节点，其权重等于当前活动节点的所有权重之和，即等于初始集合的总和。此总和对应于小于或等于下限的值。
最后得到一棵树，其权值均小于或等于下界。
示例：
-1 -5 4 -2 -> merge -5 and 4
-1 -1 -2 -> all signs equal, 2nd step: the maximum node of this sub-array correspond to the sum -4
有趣的是，我们通过以不同的顺序应用规则获得了相同的结果：
-1 -5 4 -2 -> merge 4 and -2
-1 -5 2 -> merge -5 and 2
-1 -3 -> all signs equal, 2nd step: sum equals -4