algorithm - 平衡链表列表，使它们的总和差异尽可能小？

Question

你有一个链表的链表。我们可以将高级链表称为Box，每个子链表称为Item。当然，一个 Box 将包含一个或多个 Items。每个盒子里都有一堆有重量的元素(节点)。一个盒子有一个总重量。

出于安全原因，所有箱子的重量必须尽可能接近。基本上，最重的箱子和最轻的箱子应该越小越好。你的任务是“平衡”盒子的重量。你确实有一些限制:

1. 盒子(节点)中的项目只有在它们是head 或tail 时才能移动。
2. 盒子的头部只能移动到“前一个”盒子，成为“前一个”盒子的尾部。新尾部或旧头与盒子中的元素无关。您基本上重置了节点的连接，然后以使其成为尾部的方式将其链接到“前一个”框。
3. 盒子的尾部只能移动到下一个盒子，并成为它的头部，与上面的解释类似。
4. 每个箱子都有一个最大重量(您可以假设每个箱子已经低于该最大重量)。
5. 如果您将所有项目移出，您可以“删除”盒子。
6. 您不能创建框。
7. 只要箱子不超过最大重量，箱子里就可以装尽可能多的元素。但是一个盒子不能有 0 件元素。

因此，以这个例子为例，其中每个盒子的最大重量为 15:

|       Box1              Box2            Box3   |
|   -----------        -----------        ---    |
|  | 3<->4<->5 | <--> | 4<->4<->6 | <--> | 1 |   |
|   -----------        -----------        ---    |

Box1 的总重量为 12，Box2 为 14，Box3 为 1。在理想情况下，您可以将 Box3 的头/尾移动到 Box1，但您不能这样做，因为 Box3 未“连接”到 Box1。您基本上只能向前或向后一步“移动”项目。

所以，最好的办法是把box3的头移到box2，让它成为新的尾部，所以:

|       Box1                 Box2      |
|   -----------        --------------  |
|  | 3<->4<->5 | <--> | 4<->4<->6<->1| |   
|   -----------        --------------  |

现在，总数之间的差异为 3。你不能做得更好了。

您将如何以最佳方式做到这一点？

您可以假设这就是您的“类”的样子:

class Box:
    item: Item
    next: Box
    prev: Box

class Item:
    weight: int
    next: Item
    prev: Item

编辑:

有人问如果你在 Box3 中有一个额外的数字，你会怎么做:

|       Box1              Box2             Box3      |
|   -----------        -----------        -------    |
|  | 3<->4<->5 | <--> | 4<->4<->6 | <--> | 1<->2 |   |
|   -----------        -----------        -------    |

最重和最轻箱子之间的重量是 14 - 3，即 11。

你可以在这里做两件事:

1. 您可以将 1 从 Box3 移动到 Box2。这将使差异达到 13，比之前的 11 有所增加。所以，这不是一个好主意。
2. 您可以将 6 从 box2 移动到 Box3，这样您就会得到最重的盒子 (box1) 和最轻的盒子 (box2) 之间的区别 4。这比您现在拥有的要好.

|       Box1             Box2            Box3        |
|   -----------        -------        -----------    |
|  | 3<->4<->5 | <--> | 4<->4 | <--> | 6<->1<->2 |   |
|   -----------        -------        -----------    |

编辑 2:

一位评论者问如果您遇到这种情况，但最大权重为 17 怎么办？:

|       Box1              Box2             Box3      |
|   -----------        -----------        -------    |
|  | 3<->4<->5 | <--> | 4<->4<->6 | <--> | 1<->2 |   |
|   -----------        -----------        -------    |

在这种情况下，box1:12，box2:14，box3:3。最好将 box3 的所有内容移动到 box 2，然后将 box2 的头部移动到 box1，所以:

|       Box1              Box2                Box3   |
|   -----------        ---------------        ---    |
|  | 3<->4<->5 | <--> | 4<->4<->6<->1 | <--> | 2 |   |
|   -----------        ---------------        ---    |

然后:

|       Box1                   Box2         |
|   -----------        -------------------  |
|  | 3<->4<->5 | <--> | 4<->4<->6<->1<->2 | |
|   -----------        -------------------  |

现在，box1:12，box2:17，相差 5。您可以通过移动 box2 中的 4 来改进这一点:

|       Box1                    Box2        |
|   ---------------        ---------------  |
|  | 3<->4<->5<->4 | <--> | 4<->6<->1<->2 | |
|   ---------------        ---------------  |

现在，box1: 16, box2: 13，相差3。

Answer 1

巧合的是，当我看到一个类似但不太详细的答案时，我已经在打字了。

让我们忘掉链表和框的表示。让我们把它做成带有分隔符的数组。

你的例子是:

3 4 5 | 4 4 6 | 1 2

现在关于分隔符的规则是，从一个分隔符到下一个分隔符的最大权重是 16。我们可以将分隔符向右移动多远？这很容易找到:

3 4 5 4 | 4 6 1 2 |

我们可以将分隔线向左移动多远？

| 3 4 5 4 | 4 6 1 2

现在我们可以确定每个项目之前可以出现多少个分隔符(巧合的是只有 2 个答案，但我们通常可以这样做:

3: 0-1
4: 0-1
5: 0-1
4: 0-1
4: 1-2
6: 1-2
1: 1-2
2: 1-2

现在我们在每个元素包含之后的独特状态:

min_box (skipping 0s)
max_box
current_box
finished boxes

我们的起始状态是:

min_box = maximum box size
max_box = 0
current_box = 0
finished_boxes can vary

在给定元素处，如果 current_box + current_element 不是太大，我们可以:

add current element to current box
choose whether to finish a box

如果我们选择完成一个盒子，我们:

if current_box < min_box:
    min_box = current_box
if max_box < current_box:
    max_box = current_box
increased finished_boxes by any number we want (empty boxes can get deleted at the end so don't count)

这允许我们使用动态规划遍历数组。我们需要 min_box 和 max_box 来完成最后一个元素的所有框。然后我们使用 current_box 来调整计数，并知道 min_box 和 max_box 的可能组合。寻找差异最小的那个，您就会得到答案!

但是等等。动态规划告诉我们答案有多好，但不是答案，对吧？

嗯..不。我们所要做的就是建立一个可以回答以下问题的数据结构:

by element:
    by state:
        a previous state we could have been in

我们想出了一个最佳的最终状态。通过数据结构回溯我们可以找到一条路径，它准确地告诉我们我们选择了哪些框(包括空框在哪里!)。所以我们知道最佳安排。

现在，对于获得最佳排列的最简单的方法，我们可以做的是将每个盒子边缘尽可能向左移动，然后从左到右移动元素以达到最佳排列我们选择的。

如果您想要一种更好的方法来实现最佳排列，您可以使用 A* search 来实现.

---

更新:这是用于查找框的最佳排列的 Python。

def min_boxes_by_position (elements, max_box_size):
    # Find the smallest number of boxes at each position.
    # A position is before the element at that index, and
    # after the one before that index.  There are, therefore,
    # one more positions than elements.
    cur_boxes = 0
    cur_box_size = 0
    min_boxes = [0]
    for i in range(len(elements)):
        if max_box_size < cur_box_size + elements[i]:
            # Have to start a new box.
            cur_boxes += 1
            cur_box_size = 0
        cur_box_size += elements[i]
        min_boxes.append(cur_boxes)

    return min_boxes

def optimal_arrangement (max_box_size, boxes):
    elements = []
    for box in boxes:
        elements.extend(box)

    min_boxes = min_boxes_by_position(elements, max_box_size)
    min_reversed_boxes = min_boxes_by_position(list(reversed(elements)), max_box_size)
    max_boxes = list(reversed([len(boxes) - i - 1 for i in min_reversed_boxes]))
    max_boxes[len(elements)] += 1

    # State will be a tuple (min_box_used, max_box_used, finished_boxes, current_box_size)
    begin_transition = {}
    for i in range(0, max_boxes[0] + 1):
        begin_transition[(max_box_size, 0, i, 0)] = None

    transitions = [begin_transition]
    for i in range(len(elements)):
        next_transitions = {}
        for prev_state in transitions[i].keys():
            min_box_used, max_box_used, finished_boxes, current_box_size = prev_state
            this_box = current_box_size + elements[i]
            if this_box <= max_box_size:
                # Add this to the current box, keeping it open.
                next_transitions[
                    (min_box_used, max_box_used, finished_boxes, this_box)
                ] = prev_state

                # Now calculate finishing some number of boxes here.
                if this_box < min_box_used:
                    min_box_used = this_box
                if max_box_used < this_box:
                    max_box_used = this_box
                for j in range(finished_boxes+1, max_boxes[i]+1):
                    next_transitions[
                        (min_box_used, max_box_used, j, 0)
                    ] = prev_state
        transitions.append(next_transitions)

    best_final_difference = max_box_size+1
    best_final_state = None
    for last_state in transitions[len(elements)].keys():
        min_box_used, max_box_used, finished_boxes, last_box_size = last_state
        if last_box_size == 0 and max_box_used - min_box_used < best_final_difference:
            best_final_difference = max_box_used - min_box_used
            best_final_state = last_state

    reversed_states = [best_final_state]
    for i in range(len(elements)):
        reversed_states.append(transitions[len(elements)-i][reversed_states[i]])
    box_counts = [state[2] for state in reversed(reversed_states)]
    answer = [[]]
    for i in range(len(elements)):
        if box_counts[i] < box_counts[i+1]:
            answer.append([])
        answer[box_counts[i]].append(elements[i])
    answer.pop() # Remove empty answer at end.
    return answer


print(optimal_arrangement(15, [[3, 4, 5], [4, 4, 6], [1]]))