Riddle (computer scientists, eat your hearts out)

[allchopin]

Here's the riddle... I don't have the solution but I'm hoping someone could offer ideas.

There are a given number of people, and a given number of boxes (# boxes > #people).  Each box contains different numbers of rocks, each given as well.  How would you distribute the boxes of rocks so that each person gets the closest number of rocks as everyone else (within a given threshold of deviation)?  

Example:  There are two people, three boxes.  In the three boxes there are 3 4 and 5 rocks.  The distribution would be the 3- and 4- rock boxes to one person and the 5-rock box to the other, making a difference of only 2 (7-5).

A program to do such is the eventual goal!

[bernhard]

So, now we are supposed to do your course assignments as well?

[squinchy]

Are the number of rocks in the boxes always consecutive, and is there a required percentage of people that must have at least one box? Also, what language is this to be in?

[My only progamming skill is getting lots of coloured dots to appear on a screen using QBASIC, but perhaps I can help with the algorithmic part of it.]

[allchopin]

So, now we are supposed to do your course assignments as well?

And I get all the credit.  

I suppose I should've specified a little more clearly.. the number of boxes people can get can be zero or it could be a million.  The number of rocks in each is completely arbitrary, and is simply given data.
And if you're able to find a solution, I don't care what language it is in.  English is the bare minimum  .

[squinchy]

Hm..

How about "lining up" _{(you can consider all action verbs and their objects henceforth in quotes, since they're more actions by the computer and not by the human)} all the boxes in ascending order. Then, count the number of boxes. If the number is even, set no boxes aside, if the number is odd, set one box aside (at random).

Pick two people to receive the boxes at random. Person one will take the two boxes at the end of the line, then Person two will do the same. Repeat until all boxes are taken, and then give the box that was set aside to the person with least number of boxes. If both people have the same number, give it to the person with least number of rocks. If that's the same, then I don't know what to do.

..That plan has about 80 glaring faults that I can see and probably 800 that I can't, but it's in English, and it may have a 50% chance of success.

[Shagdac]

Allchopin wrote:

How would you distribute the boxes of rocks so that each person gets the closest number of rocks as everyone else

then...

the number of boxes people can get can be zero or it could be a million.

ANSWER:  Give both of the 2 people zero boxes!
Then they both have NO rocks. That's about as close as you can get!

S

[allchopin]

Sorry - you have to give them all out.  That would be a bit too easy for $500 wouldn't it?  

[Saturn]

Sorry - you have to give them all out.  That would be a bit too easy for $500 wouldn't it?  

The problem is worth $500?  Where can I find out more about this?

[squinchy]

The problem is worth $500?  Where can I find out more about this?

0_o So either your coursework pays, or you're in a programming contest?

[super_ardua]

Ok let's process the facts.

Try getting every permutation first then see which produces the smallest difference in rocks.

Then optimise it from there on.

or

find the average amount of rocks per person,  then say everyone has to have at last one box? no.  well give everyone a box at random,  check how close we are to the average,  then if someone is higher than the avreage, give everbody a box?  no,  because ....


ok lets try a different approach
         

People	Odd	Odd	Even	Even
Rocks	Odd	Even	Odd	Even

We'll need a diffent subroutine for each:

P: odd Rocks : even

Well average is (2n + 1) / 2n so you're not going to get an integer answer so what are you going to do?  How many people do you want over the average? Iyou allocate a large box to someone,  you wnt the next one to be small.  think about


I have given enough clues.  Work it out yourself

[allchopin]

Try getting every permutation first then see which produces the smallest difference in rocks.

Well, yes, this is easy to say.  However, I neglected to mention that the program pretty much needs to be instantaneous and should run in about one second.  A computer and 100 factorial for-loops don't mix.

Then optimise it from there on.

How?

find the average amount of rocks per person,  then say everyone has to have at last one box?

Everyone will eventually get a box, but they technically don't have to.  Yet that'd be pretty dumb because the number of boxes is always greater than the number of people, so not giving a person a box would be a wrong answer for sure.

then if someone is higher than the avreage, give everbody a box?  no,  because ....

...Because people CAN be higher than the average.  What matters is that the DIFFERENCE between the highest and lowest must be a small number.  So some will be higher and some will be lower.

         

People	Odd	Odd	Even	Even
Rocks	Odd	Even	Odd	Even

We'll need a diffent subroutine for each:

P: odd Rocks : even

Well average is (2n + 1) / 2n so you're not going to get an integer answer so what are you going to do?  How many people do you want over the average? Iyou allocate a large box to someone,  you wnt the next one to be small.  think about

Hmm.
Not sure what you mean here..  an odd box should be given to people with even numbers os rocks?  And what do you mean by 'How many people do you want over the average'?  I don't think shooting for an average is the best way, because I found that way to be a dead end.  I think the iterations is the only way to do it, but making it fast and efficient, as well as optimised is what is difficult.

[super_ardua]

those were half boiled ideas.  Ignore them if you may

[super_ardua]

Crikey, this is hard.

If the approach you're working with doesn't work, it is worng so,

1. Permutations - Too slow
2. Aiming for an average? no

So you must think how we try to do it in our heads.

Facts:(check validity)

1. Not everone will have a box
2. As the total number of boxes increases to infinity, the minumum difference will decrease
3. As #people----->#boxes Minumum difference increases


Questions :

1. What does the smallest possible diference depend on?
    a) Does it increase with the number of stones in each box? No
    b) Number of people? Not really

So apart from burte force another way may to compute the minumum difference possible. But how? Dead end

Try Arranging the Boxes according to the number of rocks in them then matching the ones which contain least to most. Then arrange these pile of boxes in order of total stones in them. Match boxes higher number of stones to lower amount of stones. Until you have more piles than amount of people. Divide the pile of boxes in which each boxes has small number of stones into roughly the mount of people you have and share.  Voila ! Improve slightly on that and you may have your solution!!!!!!!!!!!