Разделите массив на две части, чтобы найти лучшее решение для получения равной или почти равной суммы целых чисел.

Question

Мне нужно решить проблему, в которой мне нужно разбить массивы на два подмассива так, чтобы сумма их весов была равна или «почти равна».

Пояснение

Если у меня есть массив [1,2,3,4,5], я могу сделать два подмножества [1,2,4] = 7 и [3,5] = 8 ИЛИ [2,5] = 7 и [1,3,4] = 8 .

Я выполнил эту часть, но, запустив dry, я узнал, что если у меня есть четное число цифр в наборе массива, это всегда дает мне неправильные ответы. Эта программа работает только для нечетного числа цифр. Чего мне не хватает?

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}\n\n", 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}\n\n", 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) в порядке убывания, чтобы добавить числа в lst1, если сумма его содержимого все еще меньше или равна частному от деления суммы основного массива на 2, в противном случае мы добавляем их (числа) в lst2, где сумма его чисел равна или почти равна упомянутому частному.

В результате у вас есть два списка, где сумма их содержимого равна или почти равна.

Answer 2

Ниже код разделит массив на 2 с равной суммой или наименьшей разницей в сумме.
Извинения за длинное решение, но он отлично работает для всех комбинаций нечетных и четных.

Явные имена переменных и Функции помогут вам понять логику c.

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("\n\nSorted 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("\n\nArray1 { " + string.Join(", ", array1) + " }\tSum => " + array1.Sum());
        Console.WriteLine("\n\nArray2 { " + 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