I have this instance:

Let's say I have two (could be more) friends, one weighing 200 pounds and another weighing 100 pounds; I won a box with 30 chocolates in a contest and I want to divide among these friends aiming at both having optimal satisfaction, measured by (chocolate)/(body weigh) ratio.

So far the problem is trivial, i give 20 chocolates to the heavier friend and 10 to the other; resulting in a chocolate/mass ratio of 1/10 for each.

But now let's assume they each had some chocolates beforehand, 3 for my thinner friend and 5 for the heavier one.

Now the problem gets complicated.

I have another instance with some 10 "friends" and the numbers are way larger. For this example I assumed the 30 chocolates were indivisible, but could also be divisible.

My question: what is this problem called? Are there any simple algorithms for it?


closed as off-topic by Marzio De Biasi, András Salamon, David Eppstein, Kaveh Oct 7 '13 at 5:34

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – András Salamon, David Eppstein, Kaveh
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Please use a more informative title. Also please check tour and help center for the scope of cstheory. $\endgroup$ – Kaveh Sep 18 '13 at 2:23

Your problem is an instance of an integer programming problem and more specifically an integer linear programming problem since your constraints are linear. For instance the second version of your problem can be written as finding integer solutions of the system \begin{align} x + y &= 30 \\ x + 5 &= 2(3 + y) \end{align} There is a huge literature on this subject...

If you allow chocolate division, you simply have a linear system of equations in $\mathbb{Q}$.


Not the answer you're looking for? Browse other questions tagged or ask your own question.