将数组一分为二，以找到获得相等或几乎相等整数和的最佳解决方案

Question

我需要解决一个问题，在这个问题中，我需要将数组拆分为两个子数组，使它们的权重之和相等或"几乎相等"。

解释

如果我有一个数组[1,2,3,4,5]，那么我可以使[1,2,4] = 7和[3,5] = 8的两个子集或[2,5] = 7和[1,3,4] = 8。

我已经完成了这一部分，但通过试运行，我知道如果数组中有偶数个数字，那么它总是给我错误的答案。此程序仅适用于奇数数字。我错过了什么？

using System.IO;
using System;
class Program
{
static void Main()
{
int[] a = {1,2,3,4};
int t;
Console.WriteLine("Original array :");
foreach (int aa in a)
Console.Write(aa + " ");
for (int p = 0; p <= a.Length - 2; p++)
{
for (int i = 0; i <= a.Length - 2; i++)
{
if (a[i] > a[i + 1])
{
t = a[i + 1];
a[i + 1] = a[i];
a[i] = t;
}
}
}
Console.WriteLine("n" + "Sorted array :");
foreach (int aa in a)
Console.Write(aa + " ");
Console.Write("n");
//   int[] arr = new int[5] { 99, 95, 93, 89, 87 };
int z, max, min, n;
// size of the array
n = 4;
max = a[0];
min = a[0];
for (z = 1; z < n; z++)
{
if (a[z] > max)
{
max = a[z];
}
if (a[z] < min)
{
min = a[z];
}
}
Console.Write("Maximum element = {0}n", max);
Console.Write("Minimum element = {0}nn", min);
int e = 0;
int f = 0;
int g = 0;
for(int i = 0; i < n; i++)
{
g = f - e;
int mm = max - min; 
{
if(g > mm)
{
e += a[i]; 
}
else if(g < mm)
{
f += a[i]; 
}
}
min++;
}
Console.Write("The possible solution is:n ");
Console.Write("First array = {0}n", e);
Console.Write("Second array = {0}nn", f); 
Console.ReadLine();
}
}

Answer 1

下面的代码片段可能会有所帮助：

var arr = new[] { 1, 2, 3, 4 };
var lst1 = new List<int>();
var lst2 = new List<int>();
var div = Math.DivRem(arr.Sum(), 2, out _);
foreach (var i in arr.OrderByDescending(x => x))
{
if (lst1.Sum() + i <= div)
lst1.Add(i);
else
lst2.Add(i);
}
Console.WriteLine(string.Join(", ", lst1.OrderBy(x => x)));
Console.WriteLine(string.Join(", ", lst2.OrderBy(x => x)));

的一些输出

---

{ 1, 2, 3, 4 }

1，4
2，3

---

{ 1, 2, 3, 4, 5 }

2，5
1，3，4

---

{ 1, 2, 3, 4, 5, 6 }

4、6
1、2、3、5

---

因此，如果源数组(arr(的内容之和仍小于或等于主数组之和除以2的商，则我们按降序迭代源数组，将数字添加到lst1中，否则，我们将它们(数字(添加到lst2中，其中源数组的数字之和等于或几乎等于上述商。

因此，您有两个列表，其中内容的总和相等或几乎相等。

Answer 2

下面的代码将数组拆分为2个和相等或和差最小的数组
对于冗长的解决方案深表歉意，但它完全适用于奇数和偶数的所有组合。

变量和函数的显式名称将帮助您理解逻辑。

using System.IO;
using System;
using System.Collections.Generic;
using System.Linq;
public class Program
{
public static void Main(string[] input)
{
int[] a = {1, 2, 9, 26, 3, 4, 12, 7, 5};
int t;
Console.WriteLine("Original array :" + string.Join(", ", a));       
for (int p = 0; p <= a.Length - 2; p++)
{
for (int i = 0; i <= a.Length - 2; i++)
{
if (a[i] > a[i + 1])
{
t = a[i + 1];
a[i + 1] = a[i];
a[i] = t;
}
}
}

Console.WriteLine("nnSorted array :" + string.Join(", ", a));

// Newly added code starts 
int[] sortedArray = a;
List<int> array1 = new List<int>();
List<int> array2 = new List<int>();
for (int index = sortedArray.Length-1 ; index >=0 ; index-- )
{
if (array1.Sum() < array2.Sum())
{
array1.Add(sortedArray[index]);
}
else if (array1.Sum() > array2.Sum())
{
array2.Add(sortedArray[index]);
}
else
{
array1.Add(sortedArray[index]);
}
}       
BalanceArray(array1, array2);

array1.Sort();
array2.Sort();
Console.WriteLine("nnArray1 { " + string.Join(", ", array1) + " }tSum => " + array1.Sum());
Console.WriteLine("nnArray2 { " + string.Join(", ", array2) + " }tSum => " + array2.Sum());
}
private static void BalanceArray(List<int> array1, List<int> array2)
{       
int sumOfArray1 = array1.Sum();
int sumOfArray2= array2.Sum();
int difference = (sumOfArray1 < sumOfArray2) ?  sumOfArray2- sumOfArray1 : sumOfArray1 - sumOfArray2;
if ( sumOfArray1 < sumOfArray2 )
{
SwapNumber(array2, array1, difference);         
}
else if ( sumOfArray1 > sumOfArray2 )
{
SwapNumber(array1, array2, difference);         
}       
}
private static void SwapNumber(List<int> biggerArray,List<int> smallerArray, int difference)
{
//Console.Write("n Difference :" + difference);        
int expectedDifference = difference /2;
//Console.Write("n Expected Difference :" + expectedDifference );
int lowerNoToSwap = 0;
int higherNoToSwap = 0;
for(int i=0; i < biggerArray.Count(); i++ )
{
if(biggerArray[i] <= expectedDifference)
{
lowerNoToSwap =  biggerArray[i];
}
else if(biggerArray[i] > expectedDifference)
{
higherNoToSwap = biggerArray[i];
break;              
}
}
if(lowerNoToSwap <= higherNoToSwap)
{
bool swapLower = (expectedDifference - lowerNoToSwap) < (higherNoToSwap - expectedDifference) ? true : false;
int numberToSwap =  swapLower ? lowerNoToSwap : higherNoToSwap;
if(numberToSwap != 0)
{
smallerArray.Add(numberToSwap);
smallerArray.Sort();
biggerArray.Remove(numberToSwap);
}
}   
}
}

示例1

Original array :1, 2, 3, 4

Sorted array :1, 2, 3, 4

before Array1 { 4, 1 }    Sum => 5

before Array2 { 3, 2 }    Sum => 5

Array1 { 1, 4 }    Sum => 5

Array2 { 2, 3 }    Sum => 5

示例2

Original array :1, 2, 3, 4, 5

Sorted array :1, 2, 3, 4, 5

Array1 { 3, 5 }    Sum => 8

Array2 { 1, 2, 4 }    Sum => 7

示例3

Original array :1, 2, 9, 26, 3, 4, 12, 7, 5

Sorted array :1, 2, 3, 4, 5, 7, 9, 12, 26

Array1 { 1, 3, 5, 26 }        Sum => 35

Array2 { 2, 4, 7, 9, 12 }        Sum => 34