基于约束条件平衡Box链表：最小化Box间总权重差值

问题背景 #

我们有一个由Box组成的双向链表，每个Box内部是一个Item双向链表：

• 每个Item节点带有权重值
• 每个Box有总权重，且存在最大权重限制（初始状态均未超出）
• 目标是通过符合规则的移动操作，让所有Box的总权重差值尽可能小（即最重与最轻Box的权重差最小）

操作约束 #

1. 仅能移动Box的head或tail节点
2. Box的head只能移动到前一个Box，并成为其tail
3. Box的tail只能移动到下一个Box，并成为其head
4. 移动后Box总权重不能超出最大限制
5. 若Box内所有Item被移出，可删除该Box
6. 不可创建新Box，且Box不能为空

核心思路 #

采用贪心迭代策略：每次找到当前权重差最大的相邻Box对，通过移动合法节点缩小二者的权重差，重复此过程直到无法再优化（或达到理论最优状态）。这种策略能逐步逼近全局最优，且完全符合操作约束的限制。

实现步骤 #

1. 预处理：给Box补充必要属性 #

为了高效计算和操作，先给Box类补充三个属性（可在初始化时完成赋值）：

• total_weight: 当前Box的总权重（初始时遍历Item计算，后续移动时实时更新）
• head: 当前Box的首Item节点
• tail: 当前Box的尾Item节点

修改后的类定义：

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

class Box:
    head: Item
    tail: Item
    total_weight: int
    next: Box
    prev: Box

2. 迭代优化流程 #

步骤1：计算当前全局状态

• 遍历所有Box，记录当前的最大权重、最小权重、总权重
• 若当前所有Box的权重已处于理论最优区间（总权重÷Box数的上下取整范围），直接终止流程

步骤2：寻找待优化的相邻Box对

遍历所有相邻的Box组合（current_box和current_box.next），优先选择以下两种权重差最大的组合：

• 左轻右重：左边Box权重远小于右边，且右边的head可移动到左边（左边总权重+该节点权重≤最大限制）
• 左重右轻：左边Box权重远大于右边，且左边的tail可移动到右边（右边总权重+该节点权重≤最大限制）

步骤3：执行节点移动操作

根据选中的组合，执行对应的移动逻辑，以下是两种核心操作的细节：

操作A：将右侧Box的head移到左侧Box的tail

def move_right_head_to_left_tail(left_box: Box, right_box: Box, max_weight: int) -> bool:
    # 检查移动合法性
    if left_box.total_weight + right_box.head.weight > max_weight:
        return False
    will_delete_right = right_box.head == right_box.tail

    # 取出右侧Box的head节点
    moved_item = right_box.head
    # 更新右侧Box的节点连接与总权重
    right_box.head = moved_item.next
    right_box.head.prev = None
    right_box.total_weight -= moved_item.weight

    # 将节点添加到左侧Box尾部
    moved_item.prev = left_box.tail
    left_box.tail.next = moved_item
    left_box.tail = moved_item
    moved_item.next = None
    left_box.total_weight += moved_item.weight

    # 删除空的右侧Box
    if will_delete_right:
        if left_box.next:
            left_box.next = right_box.next
        if right_box.next:
            right_box.next.prev = left_box
    return True

操作B：将左侧Box的tail移到右侧Box的head

def move_left_tail_to_right_head(left_box: Box, right_box: Box, max_weight: int) -> bool:
    # 检查移动合法性
    if right_box.total_weight + left_box.tail.weight > max_weight:
        return False
    will_delete_left = left_box.head == left_box.tail

    # 取出左侧Box的tail节点
    moved_item = left_box.tail
    # 更新左侧Box的节点连接与总权重
    left_box.tail = moved_item.prev
    left_box.tail.next = None
    left_box.total_weight -= moved_item.weight

    # 将节点添加到右侧Box头部
    moved_item.next = right_box.head
    right_box.head.prev = moved_item
    right_box.head = moved_item
    moved_item.prev = None
    right_box.total_weight += moved_item.weight

    # 删除空的左侧Box
    if will_delete_left:
        if right_box.prev:
            right_box.prev = left_box.prev
        if left_box.prev:
            left_box.prev.next = right_box
    return True

步骤4：重复迭代

每次执行完一次移动后，重新计算全局状态，重复步骤1-3，直到遍历所有相邻对后没有任何合法移动可以执行，或达到理论最优状态。

边界情况处理 #

1. Box空节点删除：移动后若某个Box为空，必须正确更新Box链表的前后指针，避免断链
2. 权重限制检查：每次移动前必须验证目标Box的总权重加上移动节点的权重不超过最大限制
3. 理论最优终止：当所有Box的权重都在floor(total_weight / box_count)到ceil(total_weight / box_count)之间时，无需继续操作，此时差值已最小

示例验证 #

以题目中的初始示例（最大权重15）为例：

• 初始状态：Box1(12), Box2(14), Box3(1)
• 找到权重差最大的相邻对Box2和Box3（差13），执行move_right_head_to_left_tail(Box2, Box3, 15)
• 移动后Box2总权重变为15，Box3为空被删除，剩余Box1(12)和Box2(15)，差值3，无法再执行合法移动，终止操作

内容的提问来源于stack exchange，提问作者John Lexus