Go Back   Computer Forums > General Computing > Programming
Join Computer forums Today

Thread Tools Search this Thread Display Modes
Old 01-12-2012, 09:50 AM   #1
Beta Member
Join Date: Jan 2012
Location: United Kingdom
Posts: 1
Question Weight Selection problem


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 is offline   Reply With Quote
Old 01-12-2012, 05:09 PM   #2
Site Team
berry120's Avatar
Join Date: Jul 2009
Location: England, UK
Posts: 3,422
Default 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.
berry120 is offline   Reply With Quote

best fit selection

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off

All times are GMT -5. The time now is 03:35 PM.

Powered by vBulletin® Version 3.8.8 Beta 4
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Search Engine Friendly URLs by vBSEO 3.6.0