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?

  • 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$2011-10-24
  • 0
    This looks like a [knapsack problem](http://en.wikipedia.org/wiki/Knapsack_problem).2011-10-24
  • 0
    @Gortaur Notice how $k$ is the number of weights, while $n$ is the total weight.2011-10-24
  • 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