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