[Numpy-discussion] sum up to a specific value
Pauli Virtanen
pav@iki...
Thu Jul 1 10:38:02 CDT 2010
to, 2010-07-01 kello 11:46 -0300, Renato Fabbri kirjoitti:
> just a solution (not all of them)
>
> and the application happen to come up with something like 10k values
> in the array. don care waiting, but...
As said, the problem is a well-known one, and it's not really Python or
Numpy-specific, so slightly off-topic for this list. Numpy and Scipy
don't ship pre-made algorithms for solving these.
But anyway, you'll probably find that the brute force algorithm (e.g.
the one from Vincent) takes exponential time (and exp(10000) is a big
number). So you need to do something more clever. First stop, Wikipedia,
http://en.wikipedia.org/wiki/Knapsack_problem
http://en.wikipedia.org/wiki/Subset_sum_problem
and if you are looking for pre-cooked solutions, second stop
stackoverflow,
http://stackoverflow.com/search?q=subset+sum+problem
Some search words you might want to try on Google:
http://www.google.com/search?q=subset%20sum%20dynamic%20programming
Generic advice only this time, sorry; I don't have pre-made code for
solving this at hand, but hopefully the above links give some pointers
for what to do.
--
Pauli Virtanen
More information about the NumPy-Discussion
mailing list