Algorithm to fill slots

Question

I am searching for an algorithm to fill several slots, which are already filled to some level.

• The current levels and the available quantity to fill are known
• Resulting levels should be as equal as possible, but existing level cannot be reduced
• Slots are filled from left to right, so left slots get higher level if equal level is impossible

     

The image above shows six examples, each column represents a slot. The grey area is already filled, the blue are is the expected position of the new elements.

---

I could iterate through my slots and increase the quantity on the lowest slot by 1 until the available quantity is consumed, but I wonder about how to actually calculate the new filling levels.

I am going to implement this with SQL/PL/SQL, other code is just as welcome though :)

Answer 1

Sounds like the classic Knapsack problem There's a number of different language solutions for this using different algorithms at Rosetta Code though I'm not sure there's anything in PL/SQL

Answer 2

Perhaps a greedy algorithm with randomization to break ties will be sufficient.

Let n be the number of slots you need to fill.

Step 1: Loop through the columns to identify the columns that have the least no of filled up slots. Skip the columns that are already filled up.

Step 2: If no of columns are identified in step 1 is greater than one then choose one at random.

Step 3: Set n = n-1

Repeat steps 1, 2 and 3 till n = 0 or you do not have any empty columns.

Answer 3

This is pretty straightforward.

You can visualize this as pouring water and let it fill, except for certain cases *.

1. Sort. You can also use a priority queue.
2. Keep track of the number of current min columns.
3. Get the min column with the second min column.
4. Fill the min column with either the number of available items, or up to the second min column.
5. Increment the count of current min columns.
6. Go to step 4 until all columns are at the same level, except use the number of available items, or delta (second min - first min ) times the number of current min columns. If the number of available items is not enough, just do simple math (division and remainder) to fill the columns, and use the remainder to fill from the left.
7. When all the columns are on the same level, use the simple math part described in step 6.

You should be good.

This algorithm runs in O( n log n ) time.

*Some cases this doesn't make sense, but you would still want to do it anyhow:

 #
 #
##
###
###

In that case, you would fill the third column, then the first, then the second, but of course it's not quite filling water.

Answer 4

1. Sort the columns from lowest to highest starting levels.
2. Compute the cumulative starting use for the (sorted) columns.
3. Compute for each column how much new fill will be used by filling up to the height of that column. The amount used would be the height of the column times the column index, minus the cumulative starting use of all columns before it.
4. Pick the column with index i that will use the most of your new fill without going over. Fill all columns up to column i to the height of column i (which will use the amount of fill computed in step #3 for column i), then the remaining fill goes on the first i columns evenly floor(remaining / i) plus one additional fill on the first remaining % i columns.
5. Undo sort of columns to get result.

This should take time linear in the number of columns (independent of the amount of fill).