Algorithm to fill slots

I am searching for an algorithm to fill several slots, which are already filled to some leve开发者_如何学Gol.

• 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

      Examples http://img695.imageshack.us/img695/6529/fill.png

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

---

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.

---

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.

---

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

---

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