<p>Your problem is an instance of an <a href="http://en.wikipedia.org/wiki/Integer_programming" rel="nofollow">integer programming problem</a> 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 &amp;= 30 \\
  x + 5 &amp;= 2(3 + y)
\end{align}
There is a huge literature on this subject...</p>

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

CC BY-SA 3.0
2013-09-17T16:19:01.253Z
2013-09-17T16:19:01.253Z
J.-E. Pin
<p>I have this instance:</p>

<p>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.</p>

<p>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.</p>

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

<p>Now the problem gets complicated.</p>

<p>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.</p>

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

CC BY-SA 3.0
2013-09-18T02:23:00.957Z
Please use a more informative title. Also please check [about] and [help/on-topic] for the scope of cstheory.
Kaveh
<ds.algorithms><approximation-algorithms><optimization><partition-problem>
what problem is this?
Lynx Kepler
# what problem is this?

(Asked by: username_0 on 2013-09-17)

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?

**Tags:** ds.algorithms, approximation-algorithms, optimization, partition-problem
> **Comments:**
> **username_1**: Please use a more informative title. Also please check [about] and [help/on-topic] for the scope of cstheory.  

---

## 1 answers

### Answer by username_2 on 2013-09-17. Score: 3

Your problem is an instance of an [integer programming problem](http://en.wikipedia.org/wiki/Integer_programming) 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}$.


---

