lista división en dos partes que su suma más próximos entre sí

Question

Este es un problema duro algoritmos que:

dividir la lista en 2 partes (SUM) que su suma cercana a (más) entre sí

La longitud de la lista es 1 < = n < = 100 y sus (números) pesos 1 < = w < = 250 en la pregunta.

Por ejemplo: 23 65 134 32 95 123 34

1.sum = 256

2.sum = 250

1.list = 1 2 3 7

2. list = 4 5 6

Tengo un algoritmo pero no funcionó para todas las entradas.

1. init. listas lista1 = [], list2 = []
2. elementos Ordenar (lista dada) [23 32 34 65 95 123 134]
3. pop último (max uno)
4. inserto a la lista que difiere menos

Implementación: lista1 = [], list2 = []

1. seleccione 134 lista1 inserto. list1 = [134]
2. seleccionar 123 insertar list2. porque si inserta en la lista1, la diferencia se agranda
   3. seleccione 95 e inserte list2. porque sum (list2) + 95 - sum (list1) es menor.

y así sucesivamente ...

Answer 1

El problema es la APN, pero hay un algoritmo polinómico seudo por ello, este es un problema 2-Partition, puede seguir el camino de algoritmo de tiempo polinomial seudo para sub set sum problema a resolver esto. Si el tamaño de entrada se relaciona polinomialmente con los valores de entrada, esto se puede hacer en tiempo polinomial.

En su caso (pesos < 250) es polinomio (porque peso < = 250 n => sumas < = 250 n^2).

Vamos Sum = suma de pesos, tenemos que crear dos dimensiones matriz A, entonces construir A, columna por columna

A [i, j] = TRUE si (j == peso [i] o j - peso [i] = peso [k] (k está en la lista)).

La creación de matriz con este algoritmo toma O (n^2 * suma/2).

Por fin deberíamos encontrar la columna más valiosa que tiene verdadero valor.

Aquí es un ejemplo:

artículos: {0,1,2,3} pesos: {4,7,2,8} => suma = 21 suma/2 = 10

items/weights 0| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10  
    --------------------------------------------------------- 
    |0    | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 
    |1    | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 
    |2    | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 
    |3    | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 

Así pues a [10, 2] == true la partición es de 10, 11

Este es un algoritmo que encontré here y editado un poco para resolver su problema:

bool partition(vector<int> C) { 
// compute the total sum 
int n = C.size(); 
int N = 0; 
for(int i = 0; i < n; i++) N += C[i]; 
// initialize the table 
T[0] = true; 
for(int i = 1; i <= N; i++) T[i] = false; 
// process the numbers one by one 
for(int i = 0; i < n; i++) 
    for(int j = N - C[i]; j >= 0; j--) 
    if(T[j]) T[j + C[i]] = true; 

for(int i = N/2;i>=0;i--) 
    if (T[i]) 
     return i; 
return 0; 
} 

Acabo de devolver primero T [i] que es verdadero en lugar de devolver T [N/2] (en orden máximo a mínimo).

Encontrar el camino que da este valor no es difícil.

Answer 2

Este problema es al menos tan difícil como el problema NP-completo subset sum. Tu algoritmo es un algoritmo codicioso. Este tipo de algoritmo es rápido y puede generar una solución aproximada rápidamente, pero no puede encontrar la solución exacta a un problema NP-completo.

Un enfoque de fuerza bruta es probablemente la forma más simple de resolver su problema, aunque será lento si hay demasiados elementos.

• Pruebe todas las formas posibles de dividir los elementos en dos conjuntos y calcule la diferencia absoluta en las sumas.
• Elija la partición para la cual la diferencia absoluta es mínima.

La generación de todas las particiones se puede hacer considerando la representación binaria de cada entero de 0 a 2^n, donde cada dígito binario determina si el elemento correspondiente está en la partición izquierda o derecha.

Answer 3

Puede reformular esto como knapsack problem.

Tiene una lista de artículos con un peso total M que debe montarse en una bandeja que puede contener un peso máximo de M/2. Los artículos empacados en el contenedor deben pesar tanto como sea posible, pero no más de lo que sostiene el contenedor.

Para el caso donde todos los pesos no son negativos, este problema es solo weakly NP-complete y tiene soluciones de tiempo polinomial.

Puede encontrar una descripción de las soluciones de programación dinámica para este problema en Wikipedia.