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.

We have a collection of items of weight $d_i$,

$$d_1, d_2, ..., d_k, \quad k \le 100$$

where some of the weights may be equal. Let

$$ n = \sum_{i=1}^k d_i $$

I need to figure out quickly if this collection may be split into two parts which would balance each other.

Obviously, if $[n/2] \neq n/2$, then the answer is certainly NO.

I suspect this may be a starter question and I just do not have enough background knowledge to answer it myself, so I will also appreciate all literature recommendations.

My idea is:


All items which have the same weight form a class of equivalence, there could be $1 \le m \le 100$ classes.

Let $w_1 < w_2 < \cdots < w_m$ be weights of items among each class, and let $k_1, \ldots, k_m$ be amounts of items in each class.

We introduce a boolean function

$$f(W; x_1, x_2, \ldots, x_m)$$

which equals true iff the weight $W$ can be expressed as a sum of not more than $x_1$ items of weight $w_1$, not more than $x_2$ items of weight $w_2$, $etc...$, finally, not more than $x_m$ items of weight $w_m$.

And

$$f(W;\quad 0, \ldots, 0, x_t, x_{t+1},\ldots, x_m) = \bigvee_{i=1}^{t} f(W - i* w_t;\quad0, \ldots, 0, 0, x_{t+1},\ldots, x_m)$$

Also

$$f(W; x_1, \ldots, x_m) = 0 \quad\text{ if }\quad \sum_{i=1}^{m} x_i\cdot w_i < W$$ $$f(W; x_1, \ldots, x_m) = 1 \quad\text{ if }\quad \sum_{i=1}^{m} x_i\cdot w_i = W$$

And we are interested if

$$f\left(\frac{n}{2}; k_1, k_2, \ldots, k_m\right) = \text{true}.$$

I suppose this algorithm will work and is correct (is it?), but in the worst case (10 classes, 10 items in each) we will potentially have checked ${10}^{10}$ variants, which is not a very pleasant experience.

Can it be done any faster? Maybe I even made some mistakes in my own algorithm?

Thank you very much in advance?

share|improve this question
1  
I guess with $[n/2] \neq n/2$ you mean that $n$ is odd. Then the answer is not necessary 'NO'. E.g. $d_1 = 1,d_2=2,d_3 = 3$ –  Ilya Oct 24 '11 at 9:24
    
This looks like a knapsack problem. –  Heike Oct 24 '11 at 9:40
    
@Gortaur Notice how $k$ is the number of weights, while $n$ is the total weight. –  Arthur Oct 24 '11 at 11:36
    
@Arthur: sure, you're right –  Ilya Oct 24 '11 at 11:55

1 Answer 1

up vote 1 down vote accepted

This is the partition problem. It is NP-complete.

share|improve this answer
    
Yes it is. Thank you! –  wh1t3cat1k Oct 24 '11 at 13:50

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.