Mochila con dos sumas y dos conjuntos.

16 Jul, 2023 Programación 0

Para una tarea de algoritmos, se me pide que proporcione una solución para un problema de la mochila. Tengo como entrada una lista de productos. A cada producto se le asigna un costo y un número de calorías. Por lo tanto, tengo dos conjuntos, uno de dinero y otro de kcal. Mi objetivo es elegir productos que den una suma igual de dinero y kcal.

Por ejemplo, si tengo esta entrada: (1, 3), (2, 4), (5, 8), (4, 5)

y la suma del dinero es igual a m=7 y la suma de kcal es igual a k=12, necesito elegir productos que cumplan exactamente con las dos sumas. En mi ejemplo, elegiré los productos (2, 4) y (5, 8). Mi solución solo necesita devolver verdadero si existen productos que cumplan con el requisito, de lo contrario devuelve falso. No es necesario devolver un conjunto de productos.

Ya escribí una solución utilizando la recursión basada en el problema de la suma de subconjuntos, donde vuelvo a llamar a mi función usando el último producto o no. Esta solución funciona, pero es demasiado lenta -> 2^n.

def isSubsetSum(set, n, sum, set2, sum2):
    if (sum == 0 and sum2==0):
        return True
    if (n == 0 or (sum < 0 or sum2 < 0)):
        return False

if (set[n] > sum) or (set2[n] > sum2):              # si uno de los dos valores (dinero, calorías) es mayor que la suma
    return isSubsetSum(set, n-1, sum, set2, sum2)   # evitamos usar este producto -> llamada recursiva con n-1

inclusion = isSubsetSum(set, n-1, sum-set[n], set2, sum2-set2[n]) # nos recursamos incluyendo el último producto
exclusion = isSubsetSum(set, n-1, sum, set2, sum2)  # nos recursamos excluyendo el último producto

return inclusion or exclusion

Intenté cambiar mi función de suma de subconjuntos a un enfoque de programación dinámica, pero tengo dificultades para cambiar mi función para trabajar con los dos conjuntos (conjunto de dinero y conjunto de calorías).

Hablé con los asistentes de enseñanza y me orientaron a elegir el problema de la mochila en lugar del problema de la suma de subconjuntos. Vi cómo es el enfoque de programación dinámica de la mochila, pero tengo los mismos problemas que antes con la suma de subconjuntos al cambiar el problema para que funcione con mi entrada.

Creo que me falta algo, sería genial si pudieras ayudarme a entender dónde estoy equivocado.

Gracias.

def mochila(productos, m, k): # crear una tabla de 2D para almacenar el valor máximo que se puede lograr para cada subconjunto de productos tabla = [[False] * (k+1) for _ in range(m+1)] # establecer los valores iniciales para el caso base (ningún producto seleccionado) for i in range(m+1): for j in range(k+1): if i == 0 and j == 0: tabla[i][j] = True # iterar a través de cada producto y actualizar la tabla for c, cal in productos: for i in range(m, -1, -1): for j in range(k, -1, -1): if i >= c and j >= cal: tabla[i][j] |= tabla[i-c][j-cal] # retornar True si existe un subconjunto de productos que cumpla los requisitos return tabla[m][k]

Answer

davy.ai

July 16, 2023 at 3:22 am
Parece que has identificado el enfoque correcto para resolver este problema, que es utilizando el problema de la mochila (Knapsack problem). Sin embargo, estás enfrentando dificultades para adaptar la solución para que funcione con dos conjuntos de valores.

Para resolver este problema utilizando el enfoque de la mochila, necesitas crear una tabla de 2D para almacenar el valor máximo (costo total y calorías totales) que se puede lograr con cada subconjunto de productos. Deberás iterar a través de cada producto y actualizar los valores en la tabla de manera iterativa para encontrar la solución óptima.

Para trabajar con dos conjuntos, puedes representar cada producto como una tupla (costo, calorías). También necesitarás modificar la regla de actualización de la tabla para incluir ambos conjuntos, es decir, el valor máximo en cada celda de la tabla debe considerar tanto el costo como las calorías.

Aquí tienes un ejemplo de implementación del algoritmo de la mochila para resolver este problema:
```
def mochila(productos, m, k):
    # crear una tabla de 2D para almacenar el valor máximo que se puede lograr para cada subconjunto de productos
    tabla = [[False] * (k+1) for _ in range(m+1)]

    # establecer los valores iniciales para el caso base (ningún producto seleccionado)
    for i in range(m+1):
        for j in range(k+1):
            if i == 0 and j == 0:
                tabla[i][j] = True

    # iterar a través de cada producto y actualizar la tabla
    for c, cal in productos:
        for i in range(m, -1, -1):
            for j in range(k, -1, -1):
                if i >= c and j >= cal:
                    tabla[i][j] |= tabla[i-c][j-cal]

    # retornar True si existe un subconjunto de productos que cumpla los requisitos
    return tabla[m][k]
```
Puedes llamar a esta función con tu entrada de la siguiente manera:
```
productos = [(1, 3), (2, 4), (5, 8), (4, 5)]
m = 7
k = 12
resultado = mochila(productos, m, k)
print(resultado) # True
```
Esta implementación tiene una complejidad de tiempo O(mk N), donde N es el número de productos, lo cual debería ser mucho más rápido que tu solución recursiva.

¡Espero que esto te ayude! Hazme saber si tienes alguna pregunta adicional.

Comments are closed.

es.davy.ai

¿Tienes una pregunta?

Mochila con dos sumas y dos conjuntos.

Answer

davy.ai