# Partition of a set of integer into 3 subsets of approximately equal sum

I'm having a very hard time trying to figure out how to solve this problem efficiently. Let me describe how it goes:

"A hard working mom bought several fruits with different nutritional values for her 3 kids, Amelia, Jessica and Bruno. Both girls are overweight, and they are very vicious and always leave poor Bruno with nothing, so their mother decided to share the food in the following manner:

• Amelia being the heaviest one gets the most amount of Nutritional Value.

• Jessica gets an amount equal or less than Amelia

• Bruno gets an amount equal or less than Jessica, but you need to find a way to give him the highest possible nutritional value while respecting the rule ( $A \geq J \geq B$ )"

One of the test cases given by my teacher is the following:

The fruit list has the following values { 4, 2, 1, 8, 11, 5, 1

Input:
7   -----> Number of Fruits
4 2 1 8 11 5 1 ----> Fruits Nutritional Values

Output:
1 11  ---->  One fruit, their nutritional values sum for Amelia
5     ---->  Position of the fruit in the list
3 11  ---->  Three fruits, their nutritional values sum for Jessica
1 2 6 ---->  Position of the fruits in the list
3 10  ---->  Three fruits, their nutritional values sum for Bruno
3 4 7 ---->  Position of the fruits in the list


Note: I am aware that there are several ways of diving the fruits among the kids, but it doesn't really matter as long as it follows the rule $A \geq J \geq B$.

I'm trying to make a program in C# that solves this kind of problems but I need an efficient formula to make this work. Generating all the subsets is out of the question because it is very consuming task. The list of fruits can have up to $50$ elements, $2^{50}$ is a huge number.

• This seems be a LP problem. But I am confused what the objective function should be since you have not mentioned any requirements of the solution. For instance, are you looking to distribute the food as evenly as allowable or is your goal to feed Bruno as far as possible? You can have linear constraints for everything else. Maybe I'm wrong but this is what came to my mind. – Nunoxic Jul 2 '12 at 6:23
• @Nunoxic e.g. We need 3 non-overlaping sets of booleans to indicate which foods go to which kid. We set restrains based on $A >= J >= B$ and our goal is to maximize $B$. This is a Binary Programming problem and LINGO may come in handy. – FrenzY DT. Jul 2 '12 at 8:56

Let $$x_i,\ i=1\ldots,n$$, be the list of nutritional values of the $$n$$ fruits, which I assume are nonnegative integers.

You want to partition $$\{1,\ldots,n\}$$ into three sets $$A,B,C$$ to maximize the minimum of $$x_A = \sum_{i\in A} x_i$$, $$x_B = \sum_{i \in B} x_i$$, $$x_C = \sum_{i \in C} x_i$$. This is a variant of the set-partitioning problem. It is NP-complete.

However, there is a dynamic programming algorithm that is pseudo-polynomial (i.e. polynomial in $$n$$ and $$S = \sum_{i=1}^n x_i$$). Namely, for $$1 \le m \le n$$, $$u, v \ge 0$$ with $$u+v \le \sum_{i=1}^m x_i$$, let $$T(m,u,v) = 1$$ if there are disjoint subsets $$A(m,u,v), B(m,u,v)$$ of $$\{1,\ldots,m\}$$ such that $$\sum_{i \in A(m,u,v)} x_i = u$$ and $$\sum_{i \in B(m,u,v)} x_i = v$$, $$T(m,u,v) = 0$$ otherwise. Thus $$T(1,0,0) = T(1,0,x_1) = 1,\ T(1,u,v) = 0 \text{ otherwise.}$$
For $$m > 1$$, $$T(m,u,v) = 1 \Longleftrightarrow T(m-1,u,v) + T(m-1,u-x_m,v) + T(m-1,u,v-x_m) \ge 1.$$

After computing all $$T(m,u,v)$$ using this recursion, you want to find the $$(u,v)$$ with $$u$$ as large as possible subject to $$T(m,u,v) = 1$$ and $$u \le v \le S - u - v$$.

• Hard on the eyes, Robert. Can you break it up into paragraphs, or use displays for some of the formulas, to improve readability? – Gerry Myerson Jul 2 '12 at 7:21

If you just need approximate equality, you can use the naive solution to dividing fruit:

1. Sort the fruit according to nutritional value.
2. Put the fruit with the most nutrition in basket #1.
3. Put the fruit with the next highest nutrition in basket #2.
4. Put the fruit with the next highest nutrition in basket #3.
5. Put the fruit with the next highest nutrition in the basket with the lowest total nutrition.
6. Repeat 5 until all fruit has been placed into baskets.
7. Give Amelia the most nutritious basket, Jessica the next most nutritious basket, and Bruno the least nutritious basket.

Sorting up to 50 elements is trivial, as is dividing them according to the rest of the algorithm. It's $O(n \log n)$ if nutrition values can be any non-negative integers, and $O(n)$ if you are able to effectively use any linear sorts (counting, bucket, radix, etc.) This doesn't produce an optimal division, but if you had one that did, you'd have solved most of the canonical knapsack problems, I believe, so you'd be talking about something significantly less efficient.