Solución:
Este problema se reduce al problema de la mochila 0-1, en el que intenta encontrar un conjunto con una suma exacta. La solución depende de las restricciones, en el caso general este problema es NP-Complete.
Sin embargo, si la suma máxima de búsqueda (llamémosla S) no es demasiado alto, entonces puede resolver el problema utilizando la programación dinámica. Lo explicaré usando una función recursiva y memorización, que es más fácil de entender que un enfoque de abajo hacia arriba.
Codifiquemos una función f(v, i, S), de modo que devuelve el número de subconjuntos en v[i:] eso suma exactamente a S. Para resolverlo de forma recursiva, primero tenemos que analizar la base (es decir: v[i:] esta vacio):
-
S == 0: el único subconjunto de
[]tiene suma 0, por lo que es un subconjunto válido. Debido a esto, la función debería devolver 1. -
S! = 0: Como único subconjunto de
[]tiene suma 0, no hay un subconjunto válido. Debido a esto, la función debería devolver 0.
Luego, analicemos el caso recursivo (es decir: v[i:] no está vacío). Hay dos opciones: incluir el número v[i] en el subconjunto actual, o no incluirlo. Si incluimos v[i], entonces buscamos subconjuntos que tienen suma S - v[i], de lo contrario, todavía estamos buscando subconjuntos con suma S. La función f podría implementarse de la siguiente manera:
def f(v, i, S):
if i >= len(v): return 1 if S == 0 else 0
count = f(v, i + 1, S)
count += f(v, i + 1, S - v[i])
return count
v = [1, 2, 3, 10]
sum = 12
print(f(v, 0, sum))
Comprobando f(v, 0, S) > 0, puede saber si existe una solución a su problema. Sin embargo, este código es demasiado lento, cada llamada recursiva genera dos nuevas llamadas, lo que conduce a un algoritmo O (2 ^ n). Ahora, podemos aplicar la memorización para que se ejecute en el tiempo O (n * S), que es más rápido si S no es demasiado grande:
def f(v, i, S, memo):
if i >= len(v): return 1 if S == 0 else 0
if (i, S) not in memo: # <-- Check if value has not been calculated.
count = f(v, i + 1, S, memo)
count += f(v, i + 1, S - v[i], memo)
memo[(i, S)] = count # <-- Memoize calculated result.
return memo[(i, S)] # <-- Return memoized value.
v = [1, 2, 3, 10]
sum = 12
memo = dict()
print(f(v, 0, sum, memo))
Ahora, es posible codificar una función g que devuelve un subconjunto que suma S. Para hacer esto, basta con agregar elementos solo si hay al menos una solución que los incluya:
def f(v, i, S, memo):
# ... same as before ...
def g(v, S, memo):
subset = []
for i, x in enumerate(v):
# Check if there is still a solution if we include v[i]
if f(v, i + 1, S - x, memo) > 0:
subset.append(x)
S -= x
return subset
v = [1, 2, 3, 10]
sum = 12
memo = dict()
if f(v, 0, sum, memo) == 0: print("There are no valid subsets.")
else: print(g(v, sum, memo))
Descargo de responsabilidad: esta solución dice que hay dos subconjuntos de [10, 10] eso suma 10. Esto se debe a que se supone que la primera decena es diferente a la segunda decena. El algoritmo se puede arreglar para asumir que ambas decenas son iguales (y por lo tanto responder a una), pero eso es un poco más complicado.
Sé que estoy dando una respuesta 10 años después desde que preguntaste esto, pero realmente necesitaba saber cómo hacer esto y la forma en que lo hicieron las jbernadas fue demasiado difícil para mí, así que busqué en Google durante una hora y encontré una pitón. Biblioteca itertools que hace el trabajo!
Espero que esto ayude a los futuros programadores novatos. Solo tienes que importar la biblioteca y usar la .combinations() método, es así de simple, devuelve todos los subconjuntos en un conjunto con orden, quiero decir:
Para el set [1, 2, 3, 4] y un subconjunto con longitud 3 no regresará [1, 2, 3][1, 3, 2][2, 3, 1] volverá solo [1, 2, 3]
Como desee TODOS los subconjuntos de un conjunto, puede iterarlo:
import itertools
sequence = [1, 2, 3, 4]
for i in range(len(sequence)):
for j in itertools.combinations(sequence, i):
print(j)
La salida será
() (1,) (2,) (3,) (4,) (1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4) (1 , 2, 3) (1, 2, 4) (1, 3, 4) (2, 3, 4)
¡Espero que esto ayude!
Entonces, la lógica es ordenar los números al revés, y suponga que la lista de números es l y la suma a formar es s.
for i in b:
if(a(round(n-i,2),b[b.index(i)+1:])):
r.append(i)
return True
return False
luego, pasamos por este ciclo y se selecciona un número de l en orden y digamos que es I . hay 2 casos posibles ya sea I es la parte de suma o no. Entonces, asumimos que I es parte de la solución y luego el problema se reduce a l ser l[l.index(i+1):] y s ser si entonces, si nuestra función es a (l, s) entonces llamamos a(l[l.index(i+1):] ,s-i). y si I no es parte de s entonces tenemos que formar s de l[l.index(i+1):] lista. Así que es similar en ambos casos, el único cambio es si i es parte de s, entonces s = si y de lo contrario s = s solamente.
ahora para reducir el problema de modo que en caso de que los números en l sean mayores que s los eliminemos para reducir la complejidad hasta que l esté vacío y en ese caso los números que se seleccionan no son parte de nuestra solución y regresamos false.
if(len(b)==0):
return False
while(b[0]>n):
b.remove(b[0])
if(len(b)==0):
return False
y en caso de que a l solo le quede 1 elemento, entonces puede ser parte de s y luego regresamos true o no es entonces volvemos false y el bucle pasará por otro número.
if(b[0]==n):
r.append(b[0])
return True
if(len(b)==1):
return False
tenga en cuenta en el ciclo si he usado b ... pero b es solo nuestra lista. y he redondeado siempre que es posible, por lo que no deberíamos obtener una respuesta incorrecta debido a los cálculos de punto flotante en Python.
r=[]
list_of_numbers=[61.12,13.11,100.12,12.32,200,60.00,145.34,14.22,100.21,14.77,214.35,200.32,65.43,0.49,132.13,143.21,156.34,11.32,12.34,15.67,17.89,21.23,14.21,12,122,134]
list_of_numbers=sorted(list_of_numbers)
list_of_numbers.reverse()
sum_to_be_formed=401.54
def a(n,b):
global r
if(len(b)==0):
return False
while(b[0]>n):
b.remove(b[0])
if(len(b)==0):
return False
if(b[0]==n):
r.append(b[0])
return True
if(len(b)==1):
return False
for i in b:
if(a(round(n-i,2),b[b.index(i)+1:])):
r.append(i)
return True
return False
if(a(sum_to_be_formed,list_of_numbers)):
print(r)
esta solución funciona más rápido que la explicada anteriormente. Sin embargo, esto funciona solo para números positivos. Sin embargo, también funciona bien si hay una solución; de lo contrario, se necesita mucho tiempo para salir de los bucles.
un ejemplo de ejecución es así, digamos
l=[1,6,7,8,10]
and s=22 i.e. s=1+6+7+8
so it goes through like this
1.) [10, 8, 7, 6, 1] 22
i.e. 10 is selected to be part of 22..so s=22-10=12 and l=l.remove(10)
2.) [8, 7, 6, 1] 12
i.e. 8 is selected to be part of 12..so s=12-8=4 and l=l.remove(8)
3.) [7, 6, 1] 4
now 7,6 are removed and 1!=4 so it will return false for this execution where 8 is selected.
4.)[6, 1] 5
i.e. 7 is selected to be part of 12..so s=12-7=5 and l=l.remove(7)
now 6 are removed and 1!=5 so it will return false for this execution where 7 is selected.
5.)[1] 6
i.e. 6 is selected to be part of 12..so s=12-6=6 and l=l.remove(6)
now 1!=6 so it will return false for this execution where 6 is selected.
6.)[] 11
i.e. 1 is selected to be part of 12..so s=12-1=1 and l=l.remove(1)
now l is empty so all the cases for which 10 was a part of s are false and so 10 is not a part of s and we now start with 8 and same cases follow.
7.)[7, 6, 1] 14
8.)[6, 1] 7
9.)[1] 1
solo para dar una comparación que ejecuté en mi computadora, que no es tan buena. utilizando
l=[61.12,13.11,100.12,12.32,200,60.00,145.34,14.22,100.21,14.77,214.35,145.21,123.56,11.90,200.32,65.43,0.49,132.13,143.21,156.34,11.32,12.34,15.67,17.89,21.23,14.21,12,122,134]
y
s = 2000
mi bucle corrió 1018 veces y 31 ms.
y el ciclo de código anterior se ejecutó 3415587 veces y tardó cerca de 16 segundos.
sin embargo, en caso de que no exista una solución, mi código se ejecutó durante más de unos minutos, así que lo detuve y el código anterior se ejecutó solo alrededor de 17 ms y el código anterior también funciona con números negativos.
así que creo que se pueden hacer algunas mejoras.
Nos encantaría que puedieras compartir esta noticia si si solucionó tu problema.