2010-10-18 13 views
7

Dada Un conjunto de números n[1], n[2], n[3], .... n[x] Y un número Malgoritmo para seleccionar un conjunto de números para llegar a un mínimo total

Me gustaría encontrar la mejor combinación de

n[a] + n[b] + n[c] + ... + n[?] >= M 

la combinación debe alcance el mínimo requerido para alcanzar o ir más allá de M sin ninguna otra combinación que dé un mejor resultado.

va a hacer esto en PHP así que el uso de las bibliotecas de PHP está bien. Si no, solo un algoritmo general servirá. ¡Gracias!

+0

El mejor ejemplo que puedo pensar es como tal Dado un comprobante de compras de valor M, voy a una tienda y elijo productos tales que haga uso completo del comprobante y pague el efectivo mínimo para recargar el saldo. También elegiría la combinación con la menor cantidad de productos si hay más de 1 combinación que produzca el mismo valor total. –

+0

La menor cantidad de productos para elegir sería sum {n [?] + N [c] + ...} donde sum> M. ¿Estoy equivocado? – Chris

+0

su suma> = M, la precedencia va al conjunto donde la diferencia entre suma y M es la menor. si dos conjuntos tienen la misma suma, el conjunto con el menor número de 'productos' gana –

Respuesta

1
pseudocode: 

list<set> results; 
int m; 
list<int> a; 

// ...  

a.sort(); 

for each i in [0..a.size] 
    f(i, empty_set);  

// ... 

void f(int ind, set current_set) 
{ 
    current_set.add(a[ind]); 

    if (current_set.sum > m) 
    { 
     results.add(current_set); 
    } 
    else 
    { 
     for (int i=ind + 1; i<a.size; ++i) 
     { 
      f(i, current_set); // pass set by value 

      // if previous call reached solution, no need to continue 
      if (a[ind] + current_set.sum) > m 
       break; 
     } 
    } 
} 

// choose whatever "best" result you need from results, the one 
// with the lowest sum or lowest number of elements 
+0

Esto podría funcionar, lamentablemente, no devuelve los resultados óptimos. Por ejemplo, M = 21, los números son 22, 15, 5, 3, 2, 2, 1. Si no me equivoco, el código arrojaría 2 resultados [22] y [15, 5, 3, 2, 2]. Pero la mejor respuesta sería [15,5,3,2,1] que no se consideraría? Corrígeme si me equivoco aquí. –

+0

agregó una solución menor, pero para otro problema. esa solución debería funcionar, pasa por alto todas las soluciones posibles, eliminando ramas equivocadas lo antes posible. entonces para sus entradas regresará [1, 2, 2, 3, 5, 15] [1, 2, 3, 5, 15] [1, 3, 5, 15] [1, 5, 15] [2, 2, 3, 5, 15] etc. Elija el conjunto con la suma más baja o el número más bajo de elementos o cualquiera que sea su "mejor" criterio. – Grozz

+0

Se las arregló para traducir esto al código. Funcionó bastante bien Gracias –

2

creo que un enfoque greedy algorithm funcionará. ¿Cuántos números espera tener en el set? Si es razonablemente bajo puede intentar backtrack, pero no lo recomendaría para juegos grandes.

+0

Gracias. Echaré un vistazo. Actualmente, estoy buscando un conjunto con un máximo de 136 valores (con posibilidad de crecimiento en el futuro) –

+0

Deberías ir por atrás, pero tratando de mejorar el tiempo de ejecución usando algunos trucos como ordenar primero el conjunto y luego retroceder . Avísame si necesitas ayuda. –

+0

Actualmente, la marcha atrás parece que es la mejor manera de hacerlo ... Necesito estudiarlo un poco más para ver si funciona. Gracias –

0

Creo que esto es NP-completo (no es posible encontrar una manera rápida de hacerlo en general). La forma en que formuló la pregunta me hace pensar en resolver Subset sum problems sucesivos con un número entero objetivo que aumenta constantemente desde M.

En su ejemplo, no hay un método conocido para determinar si se puede alcanzar a M. Solo una solución de fuerza bruta podría decirle que no es posible, y solo entonces podría verificar M + 1.

Sin embargo, es posible que desee mirar el DP solution, ya que esto al menos le dará una idea de cómo resolver el problema (aunque lentamente). También existe una solución approximate que será correcta si sus números son pequeños. Use esto. Finalmente, vale la pena señalar que el tamaño del problema se mide en la cantidad de bits, no en el tamaño (o suma) del conjunto.

Como se mencionó anteriormente, esto está relacionado con la Knapsack problem.

1

Este tipo de problemas se llama (un caso especial de la programación lineal entera) linear programming binaria. Es famoso NP-hard, es decir, no es eficiente de resolver en general.

Sin embargo, existen buenas solucionadores, tanto para uso comercial y libre, por ejemplo el solucionador de código abierto lpsolve al que puede llamar desde su programa.

/EDIT: La respuesta era viejo litera. Confundí los factores.

+0

No creo que esto sea un problema de programación lineal, ya que puede tener 0 o 1 de cada número, con un problema de programación lineal puede tener múltiplos fraccionarios –

+0

@Nick: maldición, tiene razón. Es un BLP. –

-1

Una solución Greedy funcionaría un pseudo:

algo(input_set , target_sum, output_set) 
    if input_set is NULL 
     error "target_sum can never be reached with all input_set" 
     return 
    the_max = maximum(input_set) 
    remove the_max from input_set 
    if the_max > target_sum 
     algo(input_set, target_sum, ouptput_set) 
     return 
    add the_max to output_set 
    algo(input_set, target_sum - the_max, output_set) 

llamada con output_set = NULL. ordenar intput_set por eficiencia.

+0

No es la solución para el problema de op. – Grozz

+0

Creo que esta solución solo funciona si quiero que los valores se sumen exactamente a target_sum. Sin embargo, en mi caso, el total está permitido más allá de target_sum. –

0

Este problema es casi exactamente el subset sum problem, que está relacionado con el problema Knapsack pero diferente, y es NP completo. Sin embargo, hay una solución lineal si todos los números son más pequeños que una constante y una aproximación de tiempo polinomial. Vea la página de wikipedia mencionada arriba.

4

Esto parece un problema clásico Dynamic Programming (también indicado por otras respuestas mencionan su similitud con 0-1 problemas de la mochila y Subset Sum).Todo se reduce a una simple elección: para cada elemento de la lista, lo usamos en nuestra suma o no. Podemos escribir una función recursiva sencilla para calcular la respuesta:

f(index,target_sum)= 
    0  if target_sum<=0 (i.e. we don't need to add anymore) 
    infinity if target_sum>0 and index is past the length of n (i.e. we have run out of numbers to add) 
    min(f(index+1,target_sum), f(index+1,target_sum-n[index])+n[index]) otherwise (i.e. we explore two choices - 1. take the current number 2. skip over the current number and take their minimum) 

Dado que esta función tiene subproblemas superpuestos (que explora las mismas subproblemas una y otra vez), es una buena idea a la función con memoize un caché para mantener los valores que ya se calcularon antes.

Aquí está el código en Python:

#! /usr/bin/env python 

INF=10**9 # a large enough number of your choice 

def min_sum(numbers,index,M, cache): 
    if M<=0: # we have reached or gone past our target, no need to add any more 
     return 0 
    elif len(numbers)==index: # we have run out of numbers, solution not possible 
     return INF 
    elif (index,M) in cache: # have been here before, just return the value we found earlier 
     return cache[(index,M)] 
    else: 
     answer=min(
      min_sum(numbers,index+1,M,cache), # skip over this value 
      min_sum(numbers,index+1,M-numbers[index],cache)+numbers[index] # use this value 
     ) 
     cache[(index,M)]=answer # store the answer so we can reuse it if needed 
     return answer 

if __name__=='__main__': 
    data=[10,6,3,100] 
    M=11 

    print min_sum(data,0,M,{}) 

Esta solución sólo devuelve la suma mínima, no los elementos reales que se utilizan para hacerlo. Puede ampliar fácilmente la idea para agregar eso a su solución.

0

La solución codiciosa funciona si la pregunta solicita el número mínimo de elementos. Pero la función máxima (..) tendrá en cuenta que cuando M es negativo, el máximo debe devolver la distancia del número a 0. (abs() del valor).

La función máxima() se puede implementar a través de un montón binario. La complejidad es O (n.logn).

Cuestiones relacionadas