Algoritmo para llenar las ranuras

Question

Estoy buscando un algoritmo para llenar varias ranuras, que ya están llenas hasta cierto nivel.

• Los niveles actuales y la cantidad disponible para llenar son conocidos
• niveles resultantes deben ser tan iguales como sea posible, pero el nivel existente no puede ser reducida
• ranuras se llenan de izquierda a derecha, las franjas horarias de modo izquierda consiguen más alto nivel si es igual nivel es imposible

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

La imagen de arriba muestra seis ejemplos, cada columna representa un espacio. El área gris ya está llena, el azul es la posición esperada de los nuevos elementos.

---

pude recorrer mis ranuras y aumentar la cantidad en la ranura más baja por 1 hasta que la cantidad disponible se consume, pero me pregunto acerca de cómo calcular realidad los nuevos niveles de llenado.

voy a poner en práctica esto con SQL/PL/SQL, otro tipo de código es tan bienvenido, aunque :)

Answer 1

suena como el clásico Knapsack problem Hay un número de diferentes soluciones de idiomas para esto utilizando diferentes algoritmos en Rosetta Code aunque No estoy seguro de que haya algo en PL/SQL

Answer 2

Tal vez sea suficiente un algoritmo codicioso con aleatorización para romper las ataduras.

Sea n la cantidad de ranuras que debe llenar.

Paso 1: Pasa por las columnas para identificar las columnas que tienen el menor número de ranuras rellenas. Omita las columnas que ya están llenas.

Paso 2: Si ninguna de las columnas identificadas en el paso 1 es mayor que una, entonces elija una al azar.

Paso 3: Ajuste n = n-1

Repita los pasos 1, 2 y 3 hasta n = 0 o no tiene ningún columnas vacías.

Answer 3

Esto es bastante sencillo.

Puede visualizar esto como verter agua y dejar que se llene, excepto en ciertos casos *.

1. Sort. También puede usar una cola de prioridad.
2. Lleve un registro del número de columnas mínimas actuales.
3. Obtenga la columna min con la segunda columna min.
4. Rellene la columna min con el número de elementos disponibles o hasta la segunda columna min.
5. Incrementa el recuento de las columnas mínimas actuales.
6. Vaya al paso 4 hasta que todas las columnas estén en el mismo nivel, excepto que use el número de elementos disponibles, o delta (segundo min - primer min) multiplicado por el número de columnas min actuales. Si la cantidad de elementos disponibles no es suficiente, simplemente haga cálculos simples (división y resto) para llenar las columnas, y use el resto para completar desde la izquierda.
7. Cuando todas las columnas están en el mismo nivel, utilice la parte matemática simple se describe en el paso 6.

Usted debe ser bueno.

Este algoritmo se ejecuta en O(n log n) tiempo.

* Algunos de los casos esto no tiene sentido, pero todavía quiere hacer de todos modos:

# 
# 
## 
### 
### 

En ese caso, se debe llenar la tercera columna, a continuación, la primera, la segunda, pero por supuesto no es agua suficiente.

Answer 4

1. Ordene las columnas desde el nivel inicial más bajo hasta el más alto.
2. Calcule el uso acumulativo de inicio para las columnas (ordenadas).
3. Calcule para cada columna la cantidad de relleno nuevo que se utilizará llenando hasta la altura de esa columna. La cantidad utilizada sería la altura de la columna multiplicada por el índice de la columna, menos el uso acumulativo inicial de todas las columnas anteriores.
4. Elija la columna con el índice i que utilizará la mayor parte de su nuevo relleno sin pasar por alto. Llene todas las columnas hasta la columna i hasta la altura de la columna i (que usará la cantidad de relleno calculada en el paso 3 para la columna i), luego el relleno restante irá en las primeras i columnas de manera uniforme floor(remaining/i) más un relleno adicional en la primera remaining % i columnas.
5. Deshace el tipo de columnas para obtener el resultado.

Esto debería llevar un tiempo lineal en el número de columnas (independientemente de la cantidad de relleno).