123

90

200

11

599

and i have to figure out the best combination to get closest to 2000. Is there a permutation generator in java? Or should i use a cloned array and try and do some sorting methods?

The Former is probably a more OO approach.

best,

M

[ September 15, 2005: Message edited by: Max Habibi ]

*sorting*has to do with this - the question is about generating

*permutations*. Or really, generating combinations sounds closer to what you want. You can Google "java combinations" or "java permutations" to get many sample algorithms of varying usefulness to you. I suspect that for this particular problem you might do better to roll your own algorithm - but it's going to take some work to figure it out. Generating all combinations using one of the algorithms you find and trying them one at a time it probably a good initial approach. If the performance is good enough, you're done. If not, you will hopefully have gained enough understanding of the complexities to consider how the algoritm could be improved. Good luck...

[ September 15, 2005: Message edited by: Jim Yingst ]

"I'm not back." - Bill Harding, *Twister*

if not, I posted something that works OK on a small range of numbers

http://forum.java.sun.com/thread.jspa?threadID=662769

see reply #20

Originally posted by Jim Yingst:

I'm not sure how muchsortinghas to do with this - the question is about generatingpermutations. Or really, generating combinations sounds closer to what you want. You can Google "java combinations" or "java permutations" to get many sample algorithms of varying usefulness to you. I suspect that for this particular problem you might do better to roll your own algorithm - but it's going to take some work to figure it out. Generating all combinations using one of the algorithms you find and trying them one at a time it probably a good initial approach. If the performance is good enough, you're done. If not, you will hopefully have gained enough understanding of the complexities to consider how the algoritm could be improved. Good luck...

[ September 15, 2005: Message edited by: Jim Yingst ]

I think Max was hinting that sorting the collection leads to a clean solution. Think about this:- "Larger the number you start with, the closer you are to the solution".

Sheriff

"I'm not back." - Bill Harding, *Twister*

Sheriff

*only*a first step. Although at this point the best route may depend on how well the original poster can work out subsequent steps for himself. Generating all combinations

*is*a valid way to solve the problem, albeit an inefficient one.

[ September 15, 2005: Message edited by: Jim Yingst ]

"I'm not back." - Bill Harding, *Twister*

Here is a list of numbers. Find the subset whose sum is closest to 2000. (...without going over the retail price... OK, not really). Of course, the example given is trivial, because the total sum is only 1023, so the answer is the entire set. Add 149, 59, 165, and 765 to the list and it becomes a more interesting problem.

I don't think that sorting is going to help, and permutations can be a bit of a bear, particularily when you are looking for all permutations, not permutations of a specific number.

Generally speaking, what you want to do is have a loop from 1 to n, where n is the number of elements in the set. For each number, you build the subsets that contain that number of elements. I found this best to be done through recursion -- iteration to achieve this is a bit hairy.

See if you can figure it out from that. (You might be able to.) If you get stuck, post your code and we will be glad to help.

Piscis Babelis est parvus, flavus, et hiridicus, et est probabiliter insolitissima raritas in toto mundo.

Originally posted by Jim Yingst:

Generating all combinationsisa valid way to solve the problem, albeit an inefficient one.

At least the way I'm reading the problem, there doesn't really seem to be any other way to do it. If your list was {1965, 1978, 35} you would have to test 1965 + 1978, 1978 + 35 and 1965 + 35 (and 1965, 1978, 35, and 1978+1965+35) to find that 1965+35 is the closest to 2000.

Thus, I suggest using that input as your test case. It is simple enough that you can do it by hand, and if you can do it by hand, you can write a program to do it.

Piscis Babelis est parvus, flavus, et hiridicus, et est probabiliter insolitissima raritas in toto mundo.

Originally posted by Joel McNary:

At least the way I'm reading the problem, there doesn't really seem to be any other way to do it. If your list was {1965, 1978, 35} you would have to test 1965 + 1978, 1978 + 35 and 1965 + 35 (and 1965, 1978, 35, and 1978+1965+35) to find that 1965+35 is the closest to 2000.

You run 2 loops. The first iteration goes through all elements, the second skips the top most, the third skips the top 2 and so on. Worst case performance:- n-squared. Much better than all combinations, which is what order of N!.

Did you see how Paul cut 87% off of his electric heat bill with 82 watts of micro heaters? |