Python动态规划绳段分配优化问题的错误排查

任务描述 #

我们有一组以整数列表形式存储的绳段，所有绳段必须被分配完毕；我们拥有无限数量的固定长度绳子，将绳段组合到绳子上时通常会产生剩余长度，例如绳子长度为10000、绳段为[2000,2000,2000,2000,1500]时，剩余长度为500。我们的目标是最小化所有绳子的总剩余长度。

初始代码 #

def max_sum_sequence(arr, l) -> tuple:
    n = len(arr)
    dp = [0] * (l + 1)

    for i in range(n):
        for j in range(l, arr[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - arr[i]] + arr[i])

    result = []
    current_sum = l
    if sum(arr) <= current_sum:
        return tuple(item for item in reversed(arr))

    for num in reversed(arr):
        if current_sum >= num and dp[current_sum - num] + num == dp[current_sum]:
            result.append(num)
            current_sum -= num
    return tuple(result)


def update_segments(arr: list, l: int) -> list[list[tuple[int], int]]:
    result: list[list[tuple[int], int]] = []
    while True:
        optimal_sequence: tuple[int] = max_sum_sequence(arr, l)
        remainder: int = length - sum(optimal_sequence)
        result.append([optimal_sequence, remainder])
        for item in optimal_sequence:
            arr.remove(item)
        if len(arr) == 0:
            return result


if __name__ == "__main__":
    remainder_summary: int = 0
    print("Enter a length:")
    length: int = 12000
    segments = [1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530,
                1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530,
                1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530,
                1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530, 1530, 3260, 3260, 3260, 3260, 3760, 3760, 1660, 1660,
                1660, 1660, 1660, 1660, 3650, 3650, 3650, 1970, 1970, 1330, 1330, 1330, 1330, 1330, 1330, 1330, 1330,
                1330, 1330, 1330, 1330, 1330, 1330, 2410, 2410, 1180, 1180, 1180, 1180, 550, 550, 550, 550]
    optimal_values: list = update_segments(segments, length)
    for item in optimal_values:
        print(f"{item[0]} - {item[1]}")
        remainder_summary += item[1]
    print(f"Final remainder = {remainder_summary}")

初始输出 #

(550, 550, 550, 550, 1180, 1180, 1180, 2410, 1330, 1970) - 550

(1180, 2410, 1330, 1660, 1660, 3760) - 0

(1330, 3650, 3760, 3260) - 0

(1970, 3650, 1660, 1660, 1530, 1530) - 0

(1330, 1330, 1330, 1330, 1330, 1330, 1330, 1330, 1330) - 30

(1330, 1330, 1660, 3260, 1530, 1530) - 1360

(1660, 3260, 3260) - 3820

(1530, 1530, 1530, 1530, 1530) - 4350

核心问题 #

第7次及后续迭代中，算法未选择可纳入的绳段来减少剩余长度，导致剩余值过大。请问这段代码存在什么错误？

2024.01.27更新代码 #

def max_sum_sequence(arr, l) -> tuple:
    n = len(arr)
    dp = [0] * (l + 1)
    choices = [[] for _ in range(l + 1)]

    for i in range(n):
        for j in range(l, arr[i] - 1, -1):
            if dp[j] < dp[j - arr[i]] + arr[i]:
                dp[j] = dp[j - arr[i]] + arr[i]
                choices[j] = choices[j - arr[i]] + [arr[i]]

    return tuple(choices[l])

def update_segments(arr: list, l: int) -> list[list[tuple[int], int]]:
    result: list[list[tuple[int], int]] = []
    while True:
        optimal_sequence: tuple[int] = max_sum_sequence(arr, l)
        remainder: int = l - sum(optimal_sequence)
        result.append([optimal_sequence, remainder])
        for item in optimal_sequence:
            arr.remove(item)
        if len(arr) == 0:
            return result


def get_optimal(length: int, segments: list[list[int,int]) -> list[list[tuple[int], int]]:
    length: int = length
    segments: list[int] = modify_segments_list(segments)
    optimal_values: list[list[tuple[int], int]] = update_segments(segments, length)
    return optimal_values

更新后输出 #

|3840--2605--2605--2940| ==> 10
|1840--1840--2430--2940--2940| ==> 10
|1840--1840--2430--2940--2940| ==> 10
|1840--1840--2430--2940--2940| ==> 10
|2430--2940--2840--3780| ==> 10
|5365--2840--3780| ==> 15
|1840--3370--3370--3370| ==> 50
|5020--3370--3545| ==> 65
|1840--2840--3545--3545| ==> 230
|3840--5020--2840| ==> 300
|3840--3840--3840| ==> 480
|3840--3780--3780| ==> 600
|2840--2840--2840--2840| ==> 640
|3780--3780--3545| ==> 895

代码错误分析 #

初始代码的问题 #

1. 回溯逻辑缺陷：max_sum_sequence函数的回溯部分，仅通过遍历反转后的数组选择元素，这种贪心式回溯无法保证找到真正的最优组合。当存在多个能达到最大和的组合时，它只会优先选数组末尾的元素，忽略其他更优组合，导致后续剩余绳段难以高效分配。
2. 局部最优陷阱：当前采用“每次选单根绳子的最优组合”的局部最优策略，但局部最优叠加后未必能得到全局最优的总剩余。比如某次选了刚好填满绳子的组合，但拆分该组合可能让后续更多绳段被合理分配，最终总剩余更小。
3. 删除元素的隐患：arr.remove(item)只会删除第一个匹配的元素，当数组有重复值时，可能误删其他位置的元素，导致后续计算的绳段集合不准确，影响组合选择。

更新代码的改进与遗留问题 #

更新后的代码通过choices数组记录每个容量对应的最优组合，解决了回溯逻辑的缺陷，但仍存在以下问题：

1. 局部最优陷阱未解决：依然采用“每次选单根绳子的最优组合”策略，未考虑全局最优分配。
2. 删除元素的问题仍存在：重复元素的删除逻辑依然可能导致绳段集合错误。
3. 语法错误：get_optimal函数的参数segments: list[list[int,int])存在语法错误，应为segments: list[list[int, int]]。

内容的提问来源于stack exchange，提问作者Frank Delan