Python 中的优化问题。动态规划

Question

我有以下任务。绳索长12000根。例如，一组段（通常大约 100 个段）。我的任务是找到这样的分段组合，最大限度地降低绳索的成本。

这是代码：

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 时，算法没有采用可以包含在其中的段来减少余数。这会发生在所有后续迭代中。对不起我的英语不好。有错误的请指出，我将不胜感激！

Answer 1

实现这一点的最佳方法是“贪婪”算法。

这基本上意味着：

• 首先选择最大的段。
• 重复执行此操作，直到使用所有段。

这就是我的解决方案：

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]


ropes = 12000

ordered_segments = sorted(segments, reverse=True)

while len(ordered_segments) > 0:
    # Initialize the list for selected segments
    selected_segments = []

    # Initialize the remaining rope length
    remaining_rope = ropes

    # Loop through the segments
    for segment in ordered_segments:
        if segment <= remaining_rope:
            # If the segment fits, add it to the selected list 
            selected_segments.append(segment)
            # and reduce the remaining rope length
            remaining_rope -= segment
        # If the remaining rope length is zero, break out of the loop
        if remaining_rope == 0:
            break

    # Output the selected segments
    print("Selected segments:", selected_segments, 
        "Remaining rope length:", remaining_rope)

    #  filter out items that are in selected_segments
    ordered_segments = [
        item for item in ordered_segments if item not in selected_segments]

这就是结果：

Selected segments: [3760, 3760, 3650, 550] Remaining rope length: 280
Selected segments: [3260, 3260, 3260, 1970] Remaining rope length: 250
Selected segments: [2410, 2410, 1660, 1660, 1660, 1660] Remaining rope length: 540
Selected segments: [1530, 1530, 1530, 1530, 1530, 1530, 1530, 1180] Remaining rope length: 110
Selected segments: [1330, 1330, 1330, 1330, 1330, 1330, 1330, 1330, 1330] Remaining rope length: 30