Divide $m$ objects with different weight in $n$ groups in order so difference in groupweight is minimal I'm trying to divide $m$ elements into $n$ groups. Each of the $m$ elements has its own weight. Those elements should be divided into $n$ groups, where following conditions should be met:


*

*groups contain elements in the same order as the given list of elements

*The difference in group weight should be minimal

*groups consist of elements wich follow eachother, without skipping any. as in A and C in one group without B would be invalid. B should be in that group aswell


An example:
elements:


*

*A: weight = 100

*B: weight = 200

*C: weight = 150

*D: weight = 75


number of groups: 3
should be grouped as: A, B, CD
 A: It can be solved in pseudo-polynomial time using dynamic programming or memoization:
Let $f(W, n)$, where $W = (w_1, ..., w_m)$, be the solution to the problem for weights in $W$ and $n$ groups, then:
$\displaystyle f(W, n) = \min_{k \leq m} \max(S_k, f((w_{k+1}, ..., w_m), n-1))$
where $S_k$ is the sum of the first $k$ weights.
That is, try forming the first group by choosing the first $k$ weights, and recursively solve the problem for the remaining weights and $n-1$ groups.
A: The problem is NP-Hard and there has a simple reduction from the partition problem
In fact, if we assume that there are only $2$ groups, then this is exactly the partition problem. So, we can reduce the partition problem to a special instance of this problem with only 2 groups. Since the partition problem is known to be NP-Hard, this problem is also hard.
However, you can solve it by dynamic programming in pseudo-polynomial time as follows. 
Let's define $P(i,j)$ to be the optimum way to partition the sequence of weights into $j$ groups starting from position $i$ such that the maximum sum in each group is minimum. And $a_i$ as the $i$th element of the list of weights given. And we want to partition them into $g$ groups.
Then $P(i,j)$ can be obtained as follows:
$$P(i,j)=\min\limits_{1\le m\le i}^{}(\max(\sum\limits_{p=i}^{m}a_p,P(m+1,j-1)))$$
You can find more details here and here (pages 9-16)
