2
$\begingroup$

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?

  • 0
    @Arthur: sure, you're right2011-10-24

1 Answers 1

1

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

  • 0
    Yes it is. Thank you!2011-10-24