0

Me estoy enfrentando a un problema estilo el de la mochila (tenemos N objetos con pesos w1,w2...) pero, en este caso, queremos dividir los objetos en dos conjuntos que pesen exactamente lo mismo. Por ejemplo, si los pesos de los objetos son {7, 12, 1, 2, 8}, habría que repartirlos en dos conjuntos de forma que cada uno sume (7 + 12 + 1 + 2 + 8)/2 = 15. En este caso, sería, por ejemplo: {7, 8} y {12, 1, 2}.

Estoy buscando hacer esto mediante búsqueda por retroceso y creo que es un problema similar al de 'subset sum' , pero no acabo de verlo.

Si alguien pudiese echarme una mano, se lo agradecería!!

Pd: EL lenguaje de programación que utilizo es Python.

2
  • Ese problema está estudidado. Se llama el "problema de la partición" (en.wikipedia.org/wiki/Partition_problem) y es NP-completo, pero tiene algoritmos que operan en tiempo pseudopolinomial (en.wikipedia.org/wiki/Pseudopolynomial_time_number_partitioning), así como aproximaciones varias por heurísticos. Aqui tienes una implementación en python (no la he revisado, no sé si es correcta)
    – abulafia
    el 22 mar. 2022 a las 17:54
  • Hola! En el enlace que me pasaste de una implementación en python, utiliza una función recursiva, pero no realiza backtracking. Conoces alguna implementación en la que si se use backtracking para resolver este problema?
    – PicaPython
    el 23 mar. 2022 a las 16:32

1 respuesta 1

2

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

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.