La forma eficiente de resolver el problema es usando programación dinámica (dynamic programming), y es equivalente a uno de los problemas clásicos: dar cambio en monedas. Hay mucha documentación al respecto, sobre todo en inglés.
Un par de enlaces, sin garantía de calidad: https://interactivepython.org/runestone/static/pythonds/Recursion/DynamicProgramming.html https://es.wikibooks.org/wiki/Programaci%C3%B3n_din%C3%A1mica/Problema_de_las_monedas_con_programaci%C3%B3n_din%C3%A1mica Si te interesa, mi recomendación es que estudies programación dinámica en general, en cuanto lo pilles, aplicarlo a tu problema es fácil. /David. 2018-01-12 21:35 GMT+01:00 Manuel A. Estevez Fernandez <stvz...@gmail.com>: > Hola a todos, tengo la siguiente necesidad: > > Encontrar una combinación de valores pertenecientes a una colección cuyo > resultado sea un numero determinado. > > Algo así: > id target valores > 1 100 20 > 1 100 30 > 1 100 50 > 1 100 15 > 1 100 45 > 1 100 60 > 2 150 75 > 2 150 75 > 2 150 100 > 3 1500 900 > 3 1500 500 > 3 1500 600 > 3 1500 1000 > 3 1500 750 > 3 1500 200 > 3 1500 300 > 3 1500 10 > 3 1500 30 > 3 1500 50 > > Toda esta información la tengo en un archivo csv. El cual leo y genero un > diccionario: > > { > id : { target : target , values : [ valores ] } > , id : { target : target , values : [ valores ] } > } > > con el siguiente codigo realizo un matriz de verdad de la longitud de la > cantidad de los valores por ID, y realizo la suma si es lo del target +1-1 > con ese vale. > > import numpy as np > import itertools > > for id in in diccionario : > for tup in itertools.product([0,1] , repeat=len(diccionario[id][' > values'])): > resultado = np.sum( np.dot( np.array(list(tup)) , np.array( > diccionario[id]['valores'] ) ) ) > if ( diccionario[id]['target'] - 1) <= resultado and resultado <= ( > diccionario[id]['target'] + 1) : > print 'ID : ', id, ' Combinacion : ' , tup , 'Valores ', > diccionario[id]['valores'] > break > > > > La problematica que tengo es que obviamente entre mas grande sea la > cantida de valores la combinaciones serán muchas más. > > Tengo la idea de utilizar un poco de paralelizar, pero no tengo idea de > como empezar. > > No sé como hacerlo o si sea posible lo siguiente: > Lanzar un proceso por ID. > -Generar una segmentación de la matriz de verdad y asignarla un subproceso > -Cuando algún subproceso encuentre un resultado válido, lo devuelva y se > detengan los subprocesos > -Avanzar al siguiente ID. > > Saludos y gracias de antemano. > > > > Manuel Alejandro Estévez Fernández > > > > _______________________________________________ > Python-es mailing list > Python-es@python.org > https://mail.python.org/mailman/listinfo/python-es > >
_______________________________________________ Python-es mailing list Python-es@python.org https://mail.python.org/mailman/listinfo/python-es
