algoritmo para seleccionar un conjunto de números para llegar a un mínimo total

Question

Dada Un conjunto de números n[1], n[2], n[3], .... n[x] Y un número M

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!

Answer 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 

Answer 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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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).