Computer Forums Weight Selection problem

 01-12-2012, 09:50 AM #1 Beta Member   Join Date: Jan 2012 Location: United Kingdom Posts: 1 Weight Selection problem Hi, I need some advice to solve a tricky weight selection problem. Imagine a scale with a known weight X on one side. There is a selection of smaller weights available of varying size. Some of the smaller weights can be of the same value. The requirement is to choose out of the set of weights the smallest number which, when placed on the other side of the scale, bring the scale closest to being balanced. I have created a brute force method which goes through every possible permutation but this can take a long time if there are a large selection of smaller weights (24 weights gives over 66 million combinations). Are there simplier and faster computational algorithms which will solve this problem? mssloan __________________ __________________
 01-12-2012, 05:09 PM #2 Site Team     Join Date: Jul 2009 Location: England, UK Posts: 3,434 Re: Weight Selection problem Err.. welcome to the realm of NP hard problems! Without going into pages about complexity theory and dynamic programming, let's just say if you find an *exact* (exact being the key there) quick way to do it then you're heading on the way to be famous and write a huge amount of mathematical papers on the subject! There are some approaches you can take though that solve it exactly sometimes and solve it close most other times - they usually fall into the realm of dynamic programming though. If you want to do further research it's the knapsack problem you're looking at (Knapsack problem - Wikipedia, the free encyclopedia), so that might help you if you want to Google around some more! __________________ Save the whales, feed the hungry, free the mallocs.

 Tags best fit selection