Highest pile of boxes (algorithm)
I have a big problem with this task:
You have n (n <= 1000). Each of them has strength and weight. The strength of a box is the maximum weight of boxes you can put on that box. What is the maximum heap height you can do with these fields?
In other words, if I have fields (x1, y1), (x2, y2), .., (xk, yk), where x_i is the field strength, I can build a heap if and only if:
x2> = y1
x3> = y1 + y2
...
xk> = y1 + y2 + ... + y_ (k-1)
Do you have any idea how to solve this? I heard that we have to find some sort of these boxes so that if we can make a bunch of boxes (a1, a2, ... ak), then always a1 <a2 <... <ak. I see that if we sort these fields, we can find the answer with simple dynamic programming. But as I said, I don't know how to sort this: \ Thanks in advance.
source to share
Here is an idea adapted from the A * approach. However, instead of finding the minimum length path, we want to find the maximum height.
Let's start with a theoretical analysis. We assume that we already have a heap with strength s1
, and we place another box on top of it with weight w2
and strength s2
. The strength of the resulting pile will be min(s1 - w2, s2)
.
Let's start with an empty pile state (height, strength, boxes) = (0, infinity, empty)
. In addition, for any state of the piles, we need an upper bound on how many more boxes can be put on this pile. One way to calculate this boundary is to use the force factor of the pile and the minimum box weight (from boxes that are not on this pile). In order to compute this heuristic efficiently, it is desirable that the sorting of boxes by their weight be desirable.
The rest is a simple application of the A * algorithm. Of all the states in the available set, select the one with the highest expected heap (= height + heuristic). Save this state if the heap is higher than your tallest heap. Calculate the resulting pile states for each field that is not already on the heap and remove the current state from the available set. Then iterations.
You have found the highest heap if none of the pile states in the available sets have the expected heap height than the current highest heap.
This approach allows the states of the piles to be ignored, which obviously cannot contribute to the tallest pile very early. Since the pile state can only be reached from one other pile state, you do not need to handle the states in the open and closed list.
source to share
Since the lowest cell must support the most weight, you want the strongest box as the lowest. For the same reasons, you need the wekaest window on top.
So, sort your boxes with "strength" as the sort key and put the strongest at the bottom, the weakest at the top.
Now, for each block, calculate the weight that it supports at its current position.
If any box has more weight than it can support, remove the heavy block above that field.
Repeat until all the fields left in the heap are ok.
EDIT
This solution is not correct (see comments) I leave it here for reference.
source to share