如何将一个数组分成三个部分，使每个部分的总和大致相等

Question

我有一个排好序的数组，想把它分成三个部分，使它们的和尽可能接近。

例如：我有这个数组：

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

那么它将被分成以下三个部分：

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

- hienvd

---

我已经成功地将一个数组分成了两部分，但是我还没有想到如何将其分成三部分。 - hienvd

10+7=17, 8+6+6=20 and 8+6+5=19 wouldn't be a better fit? - Anders Abel

根据您的示例，我认为您想要拆分数组，保持原始顺序。此外，拆分部分的总和必须几乎等于前一个/后一个值的值。 可能需要额外的信息：

• 使用哪些小数（0-10）或（0-100）或（0-无限）...
• 使用多少位小数？

- Moonlight

这是我程序中的一个问题，需要在三进制下模拟Fano加密算法，因此我需要将概率分成三部分。 - hienvd

你必须保持元素的顺序吗？如果不是，那么你就处于NP-Hard领域...我的意思是，数组中的第一个元素和最后一个元素可以在数组的相同部分吗？ - amit

Answer 1

原帖作者已经有了一个可行的解决方案（在评论中提到），可以将数组分成两个具有相等和的部分; 将其称为 split2。 三部分版本可以使用 split2 构建。

1. 向数组中添加一个新数字，该数字等于原始数字之和的三分之一。
2. 使用 split2 将数组分成两部分。
3. 其中一部分有添加的数字; 将其删除。
4. 使用 split2 将另一部分分成两部分。

- Michael J. Barber

---

算法不错，但是当源数组中所有元素的总和等于零时，它存在问题。在这种情况下，split2函数调用没有意义，因为它将精确地分割所有原始数组和新的“虚假”元素。 - HitOdessit

@Hit 有趣的观点。实际上，当totalSum为零时的情况是微不足道的：您有原始集合和两个空集合。但是，如果盲目地按照我描述的方法进行操作，可能无法获得这个微不足道的解决方案，取决于split2的工作方式。 - Michael J. Barber

Answer 2

这类问题类似于二分问题，是NP-Hard问题，但不是在强意义下的。你可以使用O(nK)算法来解决它，其中K是输入总和的大小，请参见子集和的伪多项式时间动态规划算法。另外请参见我的回答：将列表分成两个部分，使它们的总和最接近，但在您的情况下，您应该添加另一个维度来处理它。

- Saeed Amiri

Answer 3

请尝试以下代码

int total = 0, partSum = 0, partIndex = 0;
int noOfParts = 3; //Initialize the no. of parts
int[] input = { 10, 8, 8, 7, 6, 6, 6, 5 };
int[] result = new int[noOfParts]; //Initialize result array with no. of locations equal to no. of parts, to store partSums
foreach (int i in input) //Calculate the total of input array values
{
    total += i;
}
int threshold = (total / noOfParts) - (total / input.Length) / 2; //Calculate a minimum threshold value for partSum
for (int j = input.Length - 1; j > -1; j--)
{
    partSum += input[j]; //Add array values to partSum incrementally
    if (partSum >= threshold) //If partSum reaches the threshold value, add it to result[] and reset partSum  
    {
        result[partIndex] = partSum;
        partIndex += 1;
        partSum = 0;
        continue;
    }
}
if (partIndex < noOfParts) //If no. of parts in result[] is less than the no. of parts required, add the remaining partSum value
{
    result[partIndex] = partSum;
}
Array.Reverse(result);
foreach (int k in result)
{
    Console.WriteLine(k);
}
Console.Read();     

我已经使用不同的数组值（按降序排列）以及不同的部分数量（3、4、5...）进行了测试，并获得了良好的结果。

- giftcv

---

为什么我们要有这段代码？ int threshold = (total / parts)-(total / array.Length) / 2; - hienvd

只需计算一个最小阈值，使得三个总和大于该阈值。它是通过将数组的总和除以部分数（在本例中为56/3 = 18.66四舍五入为18）并减去平均值的一半（（56/8）/2 = 7/2 = 3.5四舍五入为3）来计算的。因此，在这种情况下，完整的方程式为（56/3）-（56/8）/2 = 15。 - giftcv

Answer 4

// calculate total
total = 0;
for(i = 0; i != size; ++i) {
   total += array[i];
}

// partition
n_partitions = 3;
current_partition = 1;
subtotal = array[0];
for(i = 1; i != size; ++i) {
   if(subtotal + array[i] > total / n_partitions) {
      // start new partition;
      current_partition++;
      subtotal = array[i];
   } else {
      // push to current partition
      subtotal += array[i];
   }
}

- Giovanni Funchal

Answer 5

更新了代码：

我建议的方法如下（下面附有代码）：

• 创建数据结构（集合等）来表示您需要的输出部分数量（在您的示例中为3）
• 按降序对输入数组进行排序。
• 遍历输入数组的元素，并针对每个值：
  • 选择一个输出部分将该值放入其中（这应该是当前具有最低总和的输出部分..）
  • 将该值添加到所选的输出部分中

通过上述逻辑，您将始终向具有最低总值的输出部分添加内容（这将有助于保持相似总值的部分）。

（在下面的代码示例中，我跳过了数组排序步骤，因为您的示例已经排序）

代码：

        // the input array
        int[] inputArray = new int[] { 10, 8, 8, 7, 6, 6, 6, 5 };

        // the number of parts you want
        int numberOfOutputParts = 3;

        // create the part structures
        List<Part> listOfParts = new List<Part>();

        for(int i =0; i < numberOfOutputParts; i++)
        {
            listOfParts.Add(new Part());
        }

        // iterate through each input value
        foreach (int value in inputArray)
        {
            // find the part with the lowest sum
            int? lowestSumFoundSoFar = null;
            Part lowestValuePartSoFar = null;

            foreach(Part partToCheck in listOfParts)
            {
                if (lowestSumFoundSoFar == null || partToCheck.CurrentSum < lowestSumFoundSoFar)
                {
                    lowestSumFoundSoFar = partToCheck.CurrentSum;
                    lowestValuePartSoFar = partToCheck;
                }
            }

            // add the value to that Part
            lowestValuePartSoFar.AddValue(value);
        }

上面使用的Part类的代码（虽然您可以使用更好的东西）如下：

public class Part
{
    public List<int> Values
    {
        get;
        set;
    }

    public int CurrentSum
    {
        get;
        set;
    }

    /// <summary>
    /// Default Constructpr
    /// </summary>
    public Part()
    {
        Values = new List<int>();
    }

    public void AddValue(int value)
    {
        Values.Add(value);
        CurrentSum += value;
    }
}

- Phill_P

---

@vuonghien：恭喜你解决了问题。为什么不给参与者投票呢^^。长长的源代码...。 - culithay

Answer 6

你能否尝试我的示例，这可能会对你有所帮助

我的算法： 1/ 通过输出数组的数量计算数组数字的平均值（例如：在你的帖子中，exp:value=3）

2/ 对数组数字求和，直到总和与第一步计算出的平均值之间的差距最小

3/ 重复步骤2，直到遍历完整个数组

我使用C# 3.5进行测试

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Collections;

namespace WindowsFormsApplication2
{
    public partial class Form2 : Form
    {
        public Form2()
        {
            InitializeComponent();
        }

        ArrayList inputValue = new ArrayList();
        int avgValue = 0;
        bool isFinish = false;
        private void button1_Click(object sender, EventArgs e)
        {
            #region Init data
            isFinish = false;
            avgValue = 0;
            inputValue.Clear();
            listBox1.Items.Clear();
            //assum you input valid number without space and in desc sorting order 
            string[] arrNumber = textBox1.Text.Split(new char[] { ',' }, StringSplitOptions.RemoveEmptyEntries);
            int numberOfBreak = 3;
            int record = Convert.ToInt32(arrNumber[0]);//update the record with the maximum value of the array numbers
            for (int i = 0; i < arrNumber.Length; i++)
            {
                inputValue.Add(Convert.ToInt32(arrNumber[i]));
            }

            foreach (object obj in inputValue)
            {
                avgValue += (int)obj;
            }
            avgValue = avgValue / numberOfBreak;
            #endregion
            int lastIndex = 0;
            while (!isFinish)
            {
                int index = GetIndex(lastIndex);
                string sResult = "";
                for (int i = lastIndex; i <= index; i++)
                {
                    sResult += inputValue[i].ToString() + "-";
                }
                listBox1.Items.Add(sResult);
                if (index + 1 < inputValue.Count)
                {
                    lastIndex = index + 1;
                }
                sResult = "";
            }
        }

        private int GetIndex(int startIndex)
        {
            int index = -1;
            int gap1 = Math.Abs(avgValue - (int)inputValue[startIndex]);
            int tempSum = (int)inputValue[startIndex];
            if (startIndex < inputValue.Count - 1)
            {

                int gap2 = 0;
                while (gap1 > gap2 && !isFinish)
                {
                    for (int i = startIndex + 1; i < inputValue.Count; i++)
                    {
                        tempSum += (int)inputValue[i];

                        gap2 = Math.Abs(avgValue - tempSum);
                        if (gap2 <= gap1)
                        {
                            gap1 = gap2;
                            gap2 = 0;
                            index = i;
                            if (startIndex <= inputValue.Count - 1)
                            {
                                startIndex += 1;
                            }
                            else
                            {
                                isFinish = true;
                            }
                            if (startIndex == inputValue.Count - 1)
                            {
                                index = startIndex;
                                isFinish = true;
                            }
                            break;
                        }
                        else
                        {
                            index = i - 1;
                            break;
                        }
                    }
                }


            }
            else if (startIndex == inputValue.Count - 1)
            {
                index = startIndex;
                isFinish = true;
            }
            else
            {
                isFinish = true;
            }
            return index;
        }
    }
}

- culithay

---

我看到我的样本很糟糕。它太长了 =)) - culithay