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?

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

1 Answer 1


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.