如何将一个数组分成3个部分,每个部分的总和大致相等

Question

我有一个排列的数组,我想将它分成3个部分,以便它们的总和彼此最接近.

Ex: I have this array:

    10, 8, 8, 7, 6, 6, 6, 5

so it'll be divided into 3 part like:

    p1 {10,8} sum = 18
    p2 {8,7,6} sum = 21
    p3 {6,6,5} sum = 17

Answer 1

原始海报已经有一个工作解决方案(在评论中注明)将数组分成两部分,数额相等; 叫这个split2.可以使用构建三部分版本split2.

1. 将新数字添加到数组中,该数字等于原始数字总和的三分之一.
2. 使用将数组拆分为两部分split2.
3. 一部分有添加的数字; 去掉它.
4. 使用将另一部分拆分为两部分split2.