0

de nuevo, me encuentro sin saber como optimizar el tiempo de un reto 5kyu Packing your backpack (enlace al reto).

El ejercicio trata de llenar una mochila con un límite de peso, y que tenga la mejor puntuación posible, teniendo en cuenta que cada objeto tiene un peso y una puntuación única.

Del código, lo que más tiempo consume es el del cálculo de permutaciones (combinations) que he tratado de pasarle una lista lo más depurada posible que se me haya ocurrido.

Dejo aquí mi código.

from itertools import combinations, compress, chain

def pack_bagpack(scores, weights, capacity):
    if max(weights) > capacity:
        selectors = [w < capacity for w in weights]
        weights = list(compress(weights, selectors))
        scores = list(compress(scores, selectors))
    if sum(weights) <= capacity: return sum(scores)
    combo = []
    for i in range(2, len(weights)):
#         He probado con chain, extend y concatenar, y parece que extend es el más rápido
#         combo = list(chain(combo, (c for c in combinations(weights, i) if sum(c) <= capacity)))
#         combo += list(c for c in combinations(weights, i) if sum(c) <= capacity)
        combo.extend(c for c in combinations(weights, i) if sum(c) <= capacity)
    pairs = dict(zip(weights, scores))
    combo_scores = [sum(pairs[w] for w in c) for c in combo]
    return max(combo_scores)
1
  • Codewars permite ver las resoluciones de los demás. Quizá alguna cumpla tus expectativas.
    – Mateo
    el 13 mar. a las 3:22

1 respuesta 1

0

Yo no creo que el problema esté en cual función usar de las tantas que tiene Python, me parece más un problema algorítmico.

Este es el Problema de la Mochila, en el link está el algoritmo con un seudocódigo y una "explicación", que francamente no entendí. Pero va de crear una matriz con ceros, e ir completando las celdas con valores de puntaje comparando contra el máximo posible

Digamos que tenemos las siguientes entradas:

scores = [5,4,3,2]
weights = [4,3,2,1]
capacity = 6

introducir la descripción de la imagen aquí

El seudocódigo a python sería algo como:

def pack_bagpack(scores, weights, capacity):
    n = len(scores)

    #matriz de puntaje con ceros iniciales
    puntajes = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]
   
    for i in range(1, n + 1):
        for j in range(1, capacity + 1):
            if weights[i - 1] <= j:
                puntajes[i][j] = max(puntajes[i - 1][j], scores[i - 1] + puntajes[i - 1][j - weights[i - 1]])
            else:
                puntajes[i][j] = puntajes[i - 1][j]
    return puntajes[n][capacity]

En internet deben haber varias soluciones que afrontan el problema de manera distinto, por ejemplo https://128mots.com/2021/03/29/problema-de-mochila-algoritmo-en-python-problema-de-mochila/

2
  • Revisé el código que pusiste y entendí cómo funcionaba, pero no entendía el porqué. Así que buscando a partir de los enlaces que me pasaste he llegado a un vídeo donde lo explica bastante bien, gracias a eso he podido construir mi código (es similar al tuyo) y resolver el ejercicio. Muchísimas gracias.
    – DPM
    el 13 mar. a las 17:15
  • 1
    @DPM Gracias por el video. Solo una recomendación: Existen muchos problemas de este tipo (combinatorias, permutaciones, Problemas NP), que se pueden resolver a fuerza bruta, pero en muchos casos ya existe un algoritmo que afronta el problema de un modo más eficiente. Por ejemplo sumar los números del 1 al 100 puedes resolverlo con un for, pero es más eficiente ocupar n*(n+1) /2.
    – Yussef
    el 13 mar. a las 17:27

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