Balance a list of linked-lists so the difference of their summations are as minimal as possible?

Question

You have a linked-list of linked-lists. We can call the high-level linked-list a Box, and each sub-linked-lists an Item. A Box will, of course, have one or more of Items in them. Each box has a bunch of items in it (nodes) that have a weight. A box has a total weight.

For safety reasons, all boxes' weights must be as close to each other as possible. Basically, the heaviest box and the lightest box should be as small as possible. Your task is to "balance" the boxes' weights. You do have some constrains though:

1. Items in a box (the nodes) can only be moved if they are a head or a tail.
2. The head of a box can only move to the "previous" box, and becomes the "previous" box's tail. The new tail, or old head, has no reference to the items in the box from whence it came. You basically reset the node's connections, then link it to the "previous" box in such a way that it becomes the tail.
3. The tail of a box can only move to the next box, and becomes it's head, in a similar fashion to the explanation above.
4. Each box has a maximum weight (you can assume that each box is already under that maximum weight).
5. You can "delete" boxes if you move all the items out.
6. You cannot create boxes.
7. Boxes can have as many items in them as long as the box is not above the max weight. A box cannot have 0 items though.

So, take this example, where each box has a maximum weight of 15:

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

Box1 has a total weight of 12, Box2 14, and Box3 1. In a perfect world, you would move Box3's head/tail to Box1, but you cannot do that because Box3 is not "connected" to Box1. You can only "shift" items, basically, in one step, in a forward or backward direction.

So, the best move is to shift box3's head to box2, and make it the new tail, so:

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

Now, you have the differences between the totals as 3. You cant do any better.

How would you do this in the best way possible?

You can assume this is what your "classes" looks like:

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

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

Edit:

Someone asked what you would do if you had an extra number in Box3 such that it would look like this:

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

The weight between the heaviest and lightest boxes is 14 - 3, which is 11.

You could do two things here:

1. You can move 1 from Box3 to Box2. This would make the difference 13, which is an increase from the previous 11. So, not a good idea.
2. You could move 6 from box2 to Box3, so you would have the difference between the the heaviest box (box1) and the lightest box (box2) 4. That is better than what you have now.

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

Edit 2:

A commenter asked what if you had this situation, but with a max weight of 17?:

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

In this situation, box1: 12, box2: 14, box3: 3. It would seem best to move all of box3's contents into box 2, then move the head of box2 into box1, so:

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

Then:

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

Now, box1: 12, box2: 17, which is a difference of 5. You could improve this by moving the 4 in box2:

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

Now, box1: 16, box2: 13, which is a difference of 3.

Answer 1

By coincidence I was already typing this when I saw a similar but less detailed answer posted.

Let's forget the representation in terms of linked lists and boxes. Let's make it arrays with dividers.

Your example would be:

3 4 5 | 4 4 6 | 1 2

Now the rule on dividers is that the maximum weight from one divider to the next is 16. How far to the right can we shift the dividers? That's easy to find:

3 4 5 4 | 4 6 1 2 |

How far to the left can we shift the dividers?

| 3 4 5 4 | 4 6 1 2

And now we can identify for each item how many dividers can appear before it (by coincidence there are only 2 answers, but we can do this in general:

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

And now our unique states after each element contains:

min_box (skipping 0s)
max_box
current_box
finished boxes

Our starting states are:

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

At a given element if current_box + current_element is not too large we can:

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

If we choose to finish a box we:

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)

This allows us to use dynamic programming to walk through the array. We want the min_box and max_box for having finished all boxes at the last element. We then use current_box to adjust the tally, and know the possible combinations of min_box and max_box. Look for the one with the smallest difference and you have your answer!

But wait. Dynamic programming tells us how good the answer is, but not what it is, right?

Well..no. All we have to do is build up a data structure which can answer the following question:

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

We figured out an optimal final state. Walking back through the data structure we can find a path there, which tells us exactly what boxes we chose (including where the empty ones were!). So we know the optimal arrangement.

And now for the most naive way to get to that optimal arrangement, what we can do is shift every single box edge as far to the left as it will go, then going left to right we can move elements into the optimal arrangement that we chose.

If you want a better way to get to that optimal arrangement, you can probably do it with A* search.

---

UPDATE: Here is Python to find the optimal arrangement of boxes.

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]]))

Answer 2

Instead of thinking this in terms of Box and Item, consider this as an array with multiple separators (like [3,4,5 | 4,4,6 | 1,2]), where you can move the separators but not the elements. You need to find the ideal way of placing the separators (or grouping the array elements).

This problem now becomes somewhat similar to the Matrix Chain Multiplication problem. There, you're trying to group elements like A(BC)D or (AB)(CD). Analogously, you'll do A|BC|D or AB|CD here. The main difference would be in the results returned by the sub-problem. Instead of returning the maximum possible matrix product for a sub-problem, you'll have to return the closest possible max,min weights for the sub-problem (this is just a hint, you could totally come up with something else).