Skip to main content
2 of 2
edited body
RobPratt
  • 5.4k
  • 1
  • 15
  • 25

You can solve the problem exactly as a shortest path problem in a layered network. The nodes are $(i,k)$, where $i\in\{n,\dots,1\}$ and $k\in\{1,\dots,M\}$. The (directed) arcs are from $(i,k)$ to $(j,k+1)$ with $j<i$. The idea is that traversing arc $(i,k)\to (j,k+1)$ means that $\{i,i-1,\dots,j+1\}$ comprise a part. The cost of this arc is the (absolute, or squared, or any type of) deviation from the target $n(n+1)/(2M)$. Because the network is acyclic, you can solve the problem in $O(M n^2)$ time, that is, linear in the number of arcs.

Alternatively, a greedy heuristic could be to start a new part $p+1$ whenever including the next number would make the cumulative sum exceed $pn(n+1)/(2M)$. For $n=5$ and $M=3$, this yields $5;4;3+2+1$. For $n=8$ and $M=3$, this yields $8;7+6;5+4+3+2+1$.

RobPratt
  • 5.4k
  • 1
  • 15
  • 25