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?