Finding the heaviest of N objects using M scales

Posted by cpprulez on Stack Overflow See other posts from Stack Overflow or by cpprulez
Published on 2011-01-30T14:47:21Z Indexed on 2011/01/30 15:25 UTC
Read the original article Hit count: 173

Filed under:
|
|

We have N objects and M scales. It's up to us what the objects are, and we need to position the objects on the scales so that it is undoubtful which is the heaviest object. For example, if we have 3 objects: "a", "b", "c" and 2 scales, one possible solution is "a" > "b", "b" = "c" (here "a" is the heaviest). I need an algorithm which generates such solutions given N and M. Also let's assume that "a" is always the heaviest object.

I've lost a few hours figuring out how to do it, but no matter what I figure out, there's always cases which I miss. For example, another solution is: "a" + "c" = 2 * "b", "a" > "c".

© Stack Overflow or respective owner

Related posts about algorithm

Related posts about homework