# Balancing weights with weights

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?

-
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