# Balancing two sets while items in one are unmovable

I'm working on a following problem: Given two sets containing jars, each of which is assigned a random weight (weight is a real number), find a way to balance two sets by weight, i.e. the difference in weight between two sets is minimal, given the following constraints:

• It is impossible to move jars from the set with less weight
• Not all jars from heavier set are movable
• (Optional) the difference in number of jars between two sets is minimal

I think the problem is similar to partition problem, but not 100% sure. I don't expect the complete answer, so a suggestion to the potentially right direction is appreciated. Thanks.

-
Can you give us more details about the maximum weight and whether weights are $integers$? – Inceptio Mar 20 '13 at 12:37
I've updated my question and changed the optional constraint, I got it wrong the first time. – Long Thai Mar 20 '13 at 12:41
Perhaps similar to knapsack - which numbers among $\{n_k\}_{k-1}^N$ do I need to select to get as close as possible to a fixed $B = \frac{1}{N} \sum_{k=1}^N n_k$. That would be an $\mathcal{NP}$-algorithm then, so the best you could hope for (if you need fast execution) are efficient approximations... – gt6989b Mar 20 '13 at 13:28
It's unclear how the randomness enters into the problem -- it seems like where it says "random" you meant "arbitrary"? – joriki Mar 20 '13 at 13:47
I don't really understand the difference between 2 words, but I meant any given number is acceptable. – Long Thai Mar 20 '13 at 14:03

As this is a programming problem that I encountered, my solution is not very mathematical but I hope it helps.

Define $A$ and $B$ are 2 sets of jars. A has 2 subsets $A_1$, containing jars that cannot be moved to $B$, and $A_2$, containing jars that can be moved to $B$. Define function $w(S)$ which calculates weight of set. The question is to move jars from $A_2$ to $B$ so that the different between $w(A')$ and $w(B')$ is minimal, $A'$ and $B'$ are 2 set of jars after balancing finishes.

Solution:

If $w(B) \geq w(A)$, there is no thing to do as moving jars from $A_2$ to $B$ only increases the difference. So, I assume that $w(A) \geq w(B)$.

Define $C$ is the set of all combinations of $A_2$, i.e. $C$ is the set of all combinations of jars to be moved from $A_2$ to $B$. Which means $C$ contains $\sum\limits_{k=1}^n{n\choose k}$ elements, where $n$ is the number of jars in $A_2$. For $c_i \in C$, $c'_i = A_2 \setminus c_i$ is the set of jars remaining in $A$. For each $c_i$, calculate $\overline{w_i} = \|(w(A) + w(c'_i)) - (w(B) + w(c_i))\|$ which is the weight different if the set of jars $c_i$ are moved to $B$. The answer of my question is $c_i$ with minimal $\overline{w}$.

This solution is very expensive as it tries a lot of combinations. I add following step to optimise it: let $c_i = \{a_1... a_n\}, c_j = \{a_1... a_{n+1}\}, c_k = \{a_1... a_{n+2}\}$ are 3 sets of $C$, i.e. $\{a_1... a_{n+2}\} \in A_2$. If $\overline{w_i} < \overline{w_j}$, it is not necessary to check $c_k$ as moving jar $a_{n+2}$ to $B$ only increases the distance. Which means I also exclude all combinations containing $\{a_1...a_{a+1}\}$. This step helps reduce the number of combinations needed so that increase the performance.

-