Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

up vote 0 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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