Propongo está solución. Funciona al menos para el caso expuesto:
def dividir(mochila):
suma = sum(mochila)
if suma % 2:
return None
meta = suma // 2
mochila.sort(reverse = True)
inicio = 0
while inicio < len(mochila):
# Intentamos una solución partiendo del elemento[inicio]
salida = []
i = inicio
while i < len(mochila):
parcial = sum(salida) + mochila[i]
if parcial <= meta:
salida.append(mochila[i])
if parcial == meta:
return salida
i += 1
inicio += 1
return None
Esta función retorna una lista con los elementos que suman lo deseado. La segunda lista (el resto) puede construirse a partir de ahi (queda de tarea).
Partimos validando que el conjunto tenga una solución posible. Para esto chequeamos que la suma sea par. Si no es así, retornamos None
.
Para facilitar el algoritmo, ordenamos los valores de mayor a menor. En cualquier momento la lista de salida suma un total menor a la meta.
El primer while
selecciona el elemento de partida, mientras que el segundo while
recorre los elementos posteriores buscando la solución: agregamos a la lista el elemento i-esimo y chequeamos el total. Si nos pasamos, descartamos el valor y avanzamos al siguiente.
Este ciclo avanza hasta encontrar una solución o examinar todos los valores sin encontrar una.
Si no encuentra una solución, el while
externo elige otro elemento para empezar de nuevo y repetir todo el procedimiento. Si llega al final sin encontrar la solución, entonces no hay solución.
Demo
tests = [
[10, 2],
[10, 4, 2],
[7, 12, 1, 2, 8],
[1, 2, 3, 4, 5, 6, 7, 8, 9, 11],
[2, 3, 5, 7, 11, 13, 17, 19, 21]
]
for test in tests:
print("Mochila:", test, "meta=", sum(test) // 2)
salida = dividir(test)
if salida:
print(salida, sum(salida))
else:
print("No tiene solución")
print()
produce:
Mochila: [10, 2] meta= 6
No tiene solución
Mochila: [10, 4, 2] meta= 8
No tiene solución
Mochila: [7, 12, 1, 2, 8] meta= 15
[12, 2, 1] 15
Mochila: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11] meta= 28
[11, 9, 8] 28
Mochila: [2, 3, 5, 7, 11, 13, 17, 19, 21] meta= 49
[21, 19, 7, 2] 49
Process finished with exit code 0