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)