arrays - Encuentre el número mínimo de elementos necesarios para que su suma sea igual o superior a S

algorithm subset-sum

Question

Sé que esto se puede hacer clasificando la matriz y tomando los números más grandes hasta que se cumpla la condición requerida. Eso llevaría al menos nlog (n) tiempo de clasificación.

¿Hay alguna mejora sobre nlog(n) .

Podemos asumir que todos los números son positivos.

Answer 1

1. elimine los números <S, si encuentra algún número == S, entonces resuelva
2. casillero ordenar los números <S

Suma los elementos de mayor a menor en el orden ordenado hasta que superes S.

Answer 2

Aquí hay un algoritmo que es O(n + size(smallest subset) * log(n)) . Si el subconjunto más pequeño es mucho más pequeño que la matriz, este será O(n) .

Lea http://en.wikipedia.org/wiki/Heap_%28data_structure%29 si mi descripción del algoritmo no está clara (no hay muchos detalles, pero todos los detalles están ahí).

1. Convierta la matriz en un montón dispuesto de tal manera que el elemento más grande esté disponible en el tiempo O(n) .
2. Extraiga repetidamente el elemento más grande del montón hasta que su suma sea lo suficientemente grande. Esto toma O(size(smallest subset) * log(n)) .

Es casi seguro que esta es la respuesta que esperaban, aunque no obtenerla no debería ser un factor decisivo.

Edición: Aquí hay otra variante que a menudo es más rápida, pero puede ser más lenta.

Walk through elements, until the sum of the first few exceeds S.  Store current_sum.
Copy those elements into an array.
Heapify that array such that the minimum is easy to find, remember the minimum.
For each remaining element in the main array:
    if min(in our heap) < element:
        insert element into heap
        increase current_sum by element
        while S + min(in our heap) < current_sum:
            current_sum -= min(in our heap)
            remove min from heap

Si rechazamos la mayor parte de la matriz sin manipular nuestro montón, esto puede ser hasta dos veces más rápido que la solución anterior. Pero también es posible ser más lento, como cuando el último elemento de la matriz es más grande que S.

Answer 3

Aquí hay una solución de tiempo esperado O (n) para el problema. Es algo parecido a la idea de Moron, pero no descartamos el trabajo que hizo nuestro algoritmo de selección en cada paso, y comenzamos a intentar desde un elemento potencialmente en el medio en lugar de utilizar el enfoque de duplicación repetida.

Alternativamente, es solo una quickselect con un poco de contabilidad adicional para la suma restante.

Primero, está claro que si tuviera los elementos en orden, podría elegir los artículos más grandes primero hasta que exceda la suma deseada. Nuestra solución será así, excepto que haremos todo lo posible para no descubrir la información de pedido, porque la clasificación es lenta.

Desea poder determinar si un valor determinado es el valor de corte. Si incluimos ese valor y todo lo que es mayor que él, alcanzamos o superamos S, pero cuando lo eliminamos, entonces estamos por debajo de S, entonces estamos dorados.

Aquí está el código psuedo, no lo probé para los casos de borde, pero esto da a entender la idea.

def Solve(arr, s):
  # We could get rid of worse case O(n^2) behavior that basically never happens 
  # by selecting the median here deterministically, but in practice, the constant
  # factor on the algorithm will be much worse.
  p = random_element(arr)
  left_arr, right_arr = partition(arr, p)
  # assume p is in neither left_arr nor right_arr
  right_sum = sum(right_arr)
  if right_sum + p >= s:
    if right_sum < s:
      # solved it, p forms the cut off
      return len(right_arr) + 1    
    # took too much, at least we eliminated left_arr and p
    return Solve(right_arr, s) 
  else:
    # didn''t take enough yet, include all elements from and eliminate right_arr and p
    return len(right_arr) + 1 + Solve(left_arr, s - right_sum - p)  

Answer 4

Suponiendo que los números son enteros, puede mejorar la complejidad habitual de n lg(n) de la clasificación porque en este caso tenemos la información adicional de que los valores están entre 0 y S (para nuestros propósitos, los enteros más grandes que S son los mismos que S).

Debido a que el rango de valores es finito, puede utilizar un algoritmo de clasificación no comparativo, como la Clasificación de palomas o la Clasificación de la matriz, para ir por debajo de n lg(n) .

Tenga en cuenta que estos métodos dependen de alguna función de S, por lo que si S se hace lo suficientemente grande (yn sigue siendo lo suficientemente pequeño), es mejor que vuelva a una clasificación comparativa.

Answer 5

Una mejora (asintóticamente) sobre Theta (nlogn) que puede hacer es obtener un algoritmo de tiempo O (n log K), donde K es el número mínimo requerido de elementos.

Por lo tanto, si K es constante, o diga log n, esto es mejor (asintóticamente) que la clasificación. Por supuesto, si K es n ^ epsilon, entonces esto no es mejor que Theta (n logn).

La forma de hacer esto es usar algoritmos de selección , que le pueden indicar el elemento más grande en O (n).

Ahora haga una búsqueda binaria de K, comenzando con i = 1 (la más grande) y duplicando i, etc en cada turno.

Encuentra el i más grande, encuentra la suma de los i elementos más grandes y verifica si es mayor que S o no.

De esta manera, ejecutaría las ejecuciones O (log K) del algoritmo de selección (que es O (n)) para un tiempo total de ejecución de O (n log K).