¿Qué es un algoritmo para dividir un grupo de elementos en 3 grupos separados de manera justa?

Tengo este problema en mi libro de texto: Dado un grupo de n elementos, cada uno con un valor distinto V (i), ¿cuál es la mejor manera de dividir los elementos en 3 grupos para minimizar el grupo con el valor más alto? Da el valor de este grupo más grande.¿Qué es un algoritmo para dividir un grupo de elementos en 3 grupos separados de manera justa?

Sé cómo hacer la variante de 2 pilas de este problema: solo requiere ejecutar el algoritmo de mochila hacia atrás sobre el problema. Sin embargo, estoy bastante desconcertado sobre cómo resolver este problema. ¿Alguien podría darme algún consejo?

Respuesta: Más o menos lo mismo que el 0-1 mochila, aunque 2D

Fuente

2012-01-06 Richie Li

Desde que surgió y desapareció, aquí hay un ejemplo de fracaso codicioso {100, 51, 49, 40, 30, 20, 10}. La respuesta óptima es la división perfecta, aplicar ávidamente el mayor elemento no asignado al grupo más pequeño no lo es. – ccoakley

Tengo el mismo libro de texto. Brian Dean me lo dio;) – joshim5

Tough problema de tarea. Esta es esencialmente la versión de optimización del problema de 3 divisiones.

http://en.wikipedia.org/wiki/3-partition_problem

Se está estrechamente relacionado con el embalaje contenedor, la partición y subconjunto de suma (y, como se anotó, la mochila). Sin embargo, sucede que es fuertemente NP-Complete, lo que lo hace más difícil que sus primos. De todos modos, sugiero que comiences mirando las soluciones de programación dinámica a los problemas relacionados (comenzaría con la partición, pero encontraría una explicación que no sea wikipedia de la solución DP).

Actualización: Pido disculpas. Te he engañado. El problema de 3 divisiones divide la entrada en conjuntos de 3, no 3 conjuntos. El resto de lo que dije todavía se aplica, pero con la renovada esperanza de que tu variante no sea muy np-completa.

Fuente

2012-01-06 18:07:59 ccoakley

He agregado algo de información al problema. –

@RichieLi Pregunta honesta: ¿Cuánto detalle quieres para no estropear el problema? es decir, ¿la relación de recurrencia deseada es excesiva (no es que la tenga, tendría que resolverla yo mismo)? – ccoakley

Huh, intentaré resolverlo yo mismo. Es por la tarde, así que me pondré en contacto con usted si necesito más ayuda. –

No sé acerca de "The Best" matemáticamente hablando, pero un enfoque obvio sería construir inicialmente una población de grupos con un elemento en cada grupo. Luego, mientras tenga más grupos que el número deseado de grupos finales, extraiga los dos grupos con los valores más bajos y combínelos en un nuevo grupo que agregue nuevamente a la colección. Esto es similar a cómo se construyen los árboles de compresión Huffman.

Ejemplo:

1 3 7 9 10 
becomes 
4(1+3) 7 9 10 
becomes 
9 10 11(1+3+7)

Fuente

2012-01-06 18:12:51

Aún no hemos aprendido sobre esto, así que no creo que deba usar esto en este problema. –

Pick nits: El enfoque codicioso es óptimo en el caso huffman (para la codificación de longitud variable de alfabetos fijos). Funciona razonablemente para la partición solo si los números en el problema se distribuyen muy bien (donde no puedo ser más preciso que la palabra "muy bien"). Dado que la pregunta fue etiquetada como "programación dinámica", supongo que el objetivo de la tarea no era utilizar una técnica codiciosa. – ccoakley

Sea f [i] [j] [k] indica si es posible tener valor j en el primer conjunto y valor k en el segundo conjunto, con el primero ítems.

Así que tenemos f[i][j][k] = f[i-1][j-v[i]][k] or f[i-1][j][k-v[i]].

e inicialmente tenemos f[0][0][0] = True.

por cada f[i][j][k] = True, actualice su respuesta según cómo defina bastante.

Fuente

2012-01-08 04:02:21 Topro

Pero el i-ésimo elemento podría entrar alternativamente en el tercer conjunto, por lo que creo que debería ser 'f [i] [j] [k] = f [i-1] [jv [i]] [k] o f [i -1] [j] [kv [i]] o f [i-1] [j] [k] '. –

Además, solo para deletrearlo, al considerar la solución para algunos i, j, k donde f [i] [j] [k] = Verdadero, se calcularía el peso del 3er conjunto usando s [i] - j - k, donde s [i] es la suma de los pesos de los primeros i elementos (precalculados en tiempo lineal al inicio). –

@j_random_hacker sí, tienes razón. mi error – Topro

¿Qué es un algoritmo para dividir un grupo de elementos en 3 grupos separados de manera justa?

Respuesta

Cuestiones relacionadas