[Python-es] Obtención de Sumandos para un Target a partir de una colección de valores

[Daπid]

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 <stvzito en 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 en python.org
> https://mail.python.org/mailman/listinfo/python-es
>
>
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://mail.python.org/pipermail/python-es/attachments/20180209/cea5cabb/attachment.html>