Csharp/C#教程:如何将数组分成3个部分,每个部分的总和大致相等分享


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

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

 例如:我有这个数组:       10,8,8,7,6,6,6,5  所以它将分为3部分,如:       p1 {10,8} sum = 18      p2 {8,7,6} sum = 21      p3 {6,6,5} sum = 17  

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

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

这就像two-Partition问题,即NP-Hard,但不是强烈意义上的,你可以有一个O(nK)算法,其中K是你输入和的大小,参见pseudo polynomial time algorithm for subset sum ,另见回答divide-list-in-two-parts-that-their-sum-closest-to-each-other ,但在您的情况下,您应该添加另一个维度来处理它。

 // 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]; } } 

请尝试以下代码

 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(); 

我已经用数组中的各种值(按降序排列)测试了这个值,并且对于no来说也有不同的值。 零件(3,4,5 ......)并取得了良好的效果。

更新代码:

我建议的方法如下(代码如下):

使用上述逻辑,您将始终添加具有最低总值的输出部分(这将有助于保持具有相似整体值的部分)。

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

码:

  // 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 listOfParts = new List(); 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 Values { get; set; } public int CurrentSum { get; set; } ///  /// Default Constructpr ///  public Part() { Values = new List(); } public void AddValue(int value) { Values.Add(value); CurrentSum += value; } } 

你可以试试我的样品吗,这对你有帮助

我的算法:1 /通过输出数组的数量计算数组的avg值(exp:value = 3在你的post中)

2 /对数组求和,直到Sum的最小间隙与avg值进行比较(以1 /计算)

3 /执行步骤2直到您到达数组编号的末尾

我使用C#3.5进行测试

上述就是C#学习教程:如何将数组分成3个部分,每个部分的总和大致相等分享的全部内容,如果对大家有所用处且需要了解更多关于C#学习教程,希望大家多多关注---计算机技术网(www.ctvol.com)!

 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; } } } 

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。

ctvol管理联系方式QQ:251552304

本文章地址:https://www.ctvol.com/cdevelopment/949012.html

(0)
上一篇 2021年11月17日
下一篇 2021年11月17日

精彩推荐