Optimization problem in Python. Dynamic programming

Question

I have the following task.

There is a list of segments: list[int]. All these segments must be involved. We have the length of the rope and infinite number of ropes. when we make combinations, most often there is a remainder. For example, the length of the rope is 10000, and the segments are [2000, 2000, 2000, 2000, 1500] and here we have a remainder of 500. And when there are more segments, we will use several ropes and each will have a remainder, and this is what needs to be minimized.

Here's the code:

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}")

Output:

(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

For some reason, at iteration 7, the algorithm does not take segments that can be included in it in order to reduce the remainder. And this happens in all subsequent iterations.

What is the mistake?

upd 01.27.2024

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

There is output of this problem

|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

Answer 1

I have used a "greedy" algorithm as i believe that this is a better (more optimal) approach to the problem.

This basically means:

• selecting the largest segments first.
• do this repeatedly until all the segments are used.

So this is my solution:

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
total_remaining_rope = 0

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
    
    # Output the selected segments
    print("Selected segments:", selected_segments, 
        "Remaining rope length:", remaining_rope)
    
    total_remaining_rope += remaining_rope

    # remove items from selected_segments
    for segment in selected_segments:
        ordered_segments.remove(segment)

print('--------------------------------------')
print('the total remaining rope:', total_remaining_rope)

And this is the result:

Selected segments: [3760, 3760, 3650, 550] Remaining rope length: 280
Selected segments: [3650, 3650, 3260, 1330] Remaining rope length: 110
Selected segments: [3260, 3260, 3260, 1970] Remaining rope length: 250
Selected segments: [2410, 2410, 1970, 1660, 1660, 1660] Remaining rope length: 230
Selected segments: [1660, 1660, 1660, 1530, 1530, 1530, 1530, 550] Remaining rope length: 350
Selected segments: [1530, 1530, 1530, 1530, 1530, 1530, 1530, 1180] Remaining rope length: 110
Selected segments: [1530, 1530, 1530, 1530, 1530, 1530, 1530, 1180] Remaining rope length: 110
Selected segments: [1530, 1530, 1530, 1530, 1530, 1530, 1530, 1180] Remaining rope length: 110
Selected segments: [1530, 1530, 1530, 1530, 1530, 1530, 1530, 1180] Remaining rope length: 110
Selected segments: [1530, 1530, 1530, 1530, 1530, 1530, 1530, 550, 550] Remaining rope length: 190
Selected segments: [1530, 1530, 1530, 1530, 1530, 1530, 1530] Remaining rope length: 1290
Selected segments: [1530, 1530, 1530, 1530, 1530, 1530, 1530] Remaining rope length: 1290
Selected segments: [1530, 1530, 1530, 1530, 1530, 1530, 1530] Remaining rope length: 1290
Selected segments: [1330, 1330, 1330, 1330, 1330, 1330, 1330, 1330, 1330] Remaining rope length: 30
Selected segments: [1330, 1330, 1330, 1330] Remaining rope length: 6680
--------------------------------------
the total remaining rope: 12430

You can even see hope much rope is left over at the end !