El problema de partición

Question

Tengo un conjunto de números no únicos y me gustaría dividir esos números en particiones K de manera que la suma de números en cada partición sea casi igual. Supongamos que tengo el siguiente conjunto.

{1, 2, 3, 4, 5, 6, 7, 8, 9} 

Usando Linear partition algorithm consigo siguientes particiones cuando K = 3

{ 1 2 3 4 5 } 
{ 6 7 } 
{ 8 9 } 

que se espera, pero ya que este es el algoritmo de partición lineal, cualquier cambio en el orden del conjunto de entrada cambiará de las particiones también, que Quiero evitar

Se debe minimizar la suma de elementos para cada partición. En el ejemplo anterior La suma de cada partición es 15, 13, 17

para la siguiente entrada no funciona.

{10, 20, 90, 100, 200} 

lineal algoritmo de partición da siguiéndome

{ 10 20 90 100 } 
{ 200 } 

Pero la respuesta correcta debería ser

{ 10, 200 } { 20, 90, 100 }

Answer 1

Aquí es una solución rápida codiciosos (casi óptimo para la mayoría de los casos):

1. Ordenar los elementos en orden descendente
2. Tome los primeros K elementos y ponerlos en diferentes conjuntos
3. Para el N-K siguientes elementos, los pusieron en el set con la suma más baja

en su caso con {10, 20, 90, 100, 200}, después de la clasificación se obtiene 0.123.. El algoritmo realizará el siguiente paso:

Set A Set B 
200  100 
200  190 
200  210 
210  210 

que es la solución óptima.

Answer 2

Si lo tienes de trabajo en general y sólo está buscando un comportamiento determinístico Independientemente del orden, solo ordena primero el conjunto. Todos los conjuntos que tienen el mismo orden de desaprobación serán la misma secuencia exacta después de ser ordenados.

Por supuesto, puede aumentar la complejidad de su tiempo de ejecución, pero no veo que prevenir esto sea un requisito.

Todo esto se basa en su comentario de que la disposición de los números realmente no importa. En ese punto, esto ciertamente no es lo mismo que el problema al que se vinculó, que supone que las particiones nunca requieren reorganizar los elementos.

Answer 3

Creo que prácticamente la única opción que tiene es usar fuerza bruta, posiblemente con algunas optimizaciones (como una versión modificada de the pseudo-polynomial solution to subset sum problem para K = 2) para casos simples. Tal vez hay un algoritmo mejor, pero no mucho mejor.

Al leer los artículos de Wikipedia en Partition problem y 3-partition problem, entiendo que su problema es la versión generalizada y ligeramente modificada de estos problemas, que son NP-completos.

Más específicamente, si tuviera un algoritmo eficiente para resolver su problema, también sería capaz de resolver eficientemente los dos problemas anteriores, lo cual es imposible (a menos que P = NP).

Answer 4

LeetCoder have worked en la misma definición de problema (y solución) proporcionada por Steven Skiena. Lo único es que habla en C++, por lo que se vuelve algo más fácil de entender.