complexity of dividing set of number with constraints I've been thinking about a division problem for groups that I haven't found a dynamic programming solution and I'm trying to analyze the complexity of the problem.
There is a set of $n$ positive numbers ($S$), a vector of group sizes (let's call it $Sizes$), and a parameter $Y$. Find a way for divide the $n$ numbers into groups that their size describes in $Sizes$ s.t. the $constraint$ in close as possible to $Y$.
For example, $ S = \{1,1,2,2,3,4,4,7,9,11\}$, $Sizes = [2,2,3,3]$, $Y=2$ and $constraint =$ the variance of the group. Of course that the $constraint$ could be changed in other cases. But this is representative example.
Has this problem any dynamic programming solution? or that the complexity is exponential (which means $NP$ problem)?
Which approximation approaches can help me in this case?
Thanks in advance!
The difficulty of your problem heavily depends on &quot;constraint&quot;.
For example if $n=3k$, $\text{size}=[\underbrace{3,3,3,...}_{k\text{ times}}]$, and the constraint is that the sum of the numbers each group must be equal, then your problem is strongly NP-hard since it is exactly $3$-partition.
The same problem with groups of size $2$ is polynomial.
Notice that both problems are in $\mathsf{NP}$ and that being in $\mathsf{NP}$ does not mean that the complexity to solve it is exponential.