scm007

OK, here is what I need, but I don't really know how to get Java to do it for me. I have a data set of 2000 numbers, some positive, some negative. I need to find one summation (if possible) of 1500 numbers which is equal to zero. And I need to do it very efficiently. Thanks!

Ooble

Is this a homework assignment?

C'mon, man, show us you've tried, at least. Google a bit. Think.

__________________
Me :: You :: Them

alcdotcom

You want to find 1500 out of the 2000 that sum to zero (if possible), yes? To echo Ooble, can you show us what you've got so far?

scm007

No this isn't a homework assignment, it's something that my dad uses in his business and would save him a lot of time. I don't know how to get started. Actually, the problem is different than I stated, my apologies. There are x numbers, all of them greater than zero, and all of them some dollar amount so like 1452.32, then the user would define a number and the program would find the summation of numbers which is closest to the defined number. If that would require too much computing power, then I guess the user could define a range and then the program would find a solution in that range using a semi random sampling, so that the program just doesn't sum all of the smallest numbers. Can anybody help me wit hthat?

alcdotcom

Well, there are probably really efficient ways of doing this, and hopefully someone with a better knowledge of algorithms than I will post one. The easy way of doing it would be just to test every combination x sets of numbers in the array and get the combintion closest to the required value. Then, test every combination of x+1 sets of numbers in the array, then X+2, then X+3 then ... finally X+N where N < ( (array size) / 2 ). Since my solution requires testing all combinations then there is no need to sort the array. This is not a very efficient way of doing it and a very large array might take some time. Another consideration is what to do if a combination is exactly the same as the required number. Do you stop there or do you test to see if there is another combination that is exactly the same as the required number. If there is more than one, then which one will be chosen? This may not matter, but since I don't know the context of the problem I thought I'd bring it up as a possible headache.

Vinaaron

I think I know the solution for this one.
We've done this already in algorithm course.
I'll try to see if it is still in my archive...

__________________
Contented with little, yet wishing for more..

Klipt

You can find solutions to within a certain resolution (i.e. rounding intermediate figures to, say, the nearest dollar) using dynamic programming. The better the resolution the more memory you need, so there is a limit. It also limits the range of numbers you can test (e.g. less than $1 000 000). But it will run very fast.

It's basically a special case of the knapsack problem (with 0 cost - or the bin packing problem with 1 bin). Try reading these:

http://en.wikipedia.org/wiki/Knapsack_problem
http://en.wikipedia.org/wiki/Knapsac...mming_solution

If you need an example just ask.

EDIT: if the total can be bigger than the figure you want then it's not technically a knapsack problem, but you can change the algorithm without too much difficulty.

scm007

Klipt, thanks for the info!

Vinaaron, could you find it?

Also I could pay someone for their time if they wrote this program. Essentially there is an Excel spreadsheet with 1000-10000 entries. Each of which has a code, a price, and a risk. Then the program would go through and find a solution set such that the total price as specified by the user is in some range AND the weighted risk, i.e. the sum of (risk*price)/(total price) for all prices in the solution set is in some range. Then the program would output the corresponding codes for the entries which validate these criteria. Could anybody do this?

Infinite Recursion

Since these values are stored in Excel (per your other post)... why code in Java? PM me with a figure, and we'll talk about a solution.
\

__________________
http://jasonpowers.net

"There are a thousand hacking at the branches of evil to one who is striking at the root."

scm007

I just wrote it in the Java forum because I had the intention of doing it myself, and Java is hte only programming language that I know anything about, but very little. It would probably be easier just to pay someone, but I can't really afford to pay a lot, so just give me an estimate on how long it will take you and I will give you a figure. How much do you think it would cost?