# Constrained disjoint subsets

How to partition $n$ weighted elements into $m$ disjoint subsets such that the sum of weight of all elements in a subset is less than equals to the capacity of $j$th subset ($c_j$) . It is given that $m<n$

Example: $x_1,x_2,x_3$ are weights of 3 elements (here $n=3$). Divide these 3 elements into 2 subsets (here $m=2$) such that the $sum(X_1)<= c_1$ and $sum(X_2)<= c_2$. Here $sum(X_1)$ and $sum(X_2)$ are the summation of weights of all elements in subset 1 and 2 respectively.

The answer of the given problem is ($x_1,x_3$),($x_2$) if $x_1+x_3<=c_1$ and $x_2<=c_2$

-
I have a guess that this is NP-complete, being related to some scheduling / bin-packing problems. Oh wait actually, with $m = 2$ it's the subset-sum problem, so clearly NP-complete. – ShreevatsaR Jan 29 '14 at 4:36

This problem is NP-complete, which means that there is no algorithm that runs in time polynomial in the input size (which is the size (length) of the weights $x_i$ and $c_j$).
That this is in NP is straightforward: given a purported solution, we can easily verify whether the solution satisfies the constraint. To see that this is NP-hard as well, we can reduce the subset-sum problem to this one. Given an instance of the subset-sum problem, which is a set of integers (= weights $x_i$) and a desired sum $s$, cast it as your problem by taking $m = 2$, and the capacities to be $c_1 = s$ and $c_2 = \sum_i x_i - s$. Then, it is possible to partition the $n$ weights $x_i$ into two sets having total weight bounded by $c_1$ and $c_2$, if and only if there exists a subset of the weights $x_i$ whose sum is $s$.
That proves that it is NP-complete. However, we can, for small $n$ and $m$, write down a dynamic-programming algorithm to solve the problem. A $O(n^{m-1})$ (or so) algorithm is straightforward, but there may also exist algorithms polynomial in $m$ and $n$.