Weight Selection problem

[mssloan]

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

[berry120]

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!