Распределение элементов по трем кучам с минимальной разницей

#c_sharp #алгоритм

  Необходимо достичь минимальной возможной разницы между суммами значений элементов
в кучках


Вот то, что получилось у меня, Принцип работы - запихивание элемента в наименьшую кучку:

int item0 = 0, item1 = 0, item2 = 0; //Кучки
        List templist = new List() { 20, 19, 14, 13, 11, 9, 6 };
        foreach (var item in templist)
        {
            if (item0 <= item1 && item0 <= item2)
            {
                item0 += item;
            }
            else if(item1 <= item0 && item1 <= item2)
            {
                item1 += item;
            }
            else
            {
                item2 += item;
            }
        }

        Console.WriteLine("Первая кучка: " + item0);
        Console.WriteLine("Вторая кучка: " + item1);
        Console.WriteLine("Третья кучка: " + item2);
        Console.ReadKey();


Код работает быстро, но точность не полная, он выводит:
А самый оптимальный вариант - 29, 31, 32. Это достигается путем таких сложений:
29 = 20 + 9
31 = 14 + 6 + 11
32 = 19 + 13  



Как можно добиться такого результата?
P.S. количество элементов списка может меняться, их значение тоже.
P.P.S Список по умолчанию дается не сортированным, сделаем вид, что механизм сортировки
в данное коде есть, но опущен.
    

Ответы

Ответ 1

Добавлю немножко динамики. 

public Tuple FindMin(int[] numbers, Tuple
currentMin, int curIndex, int store1, int store2, int store3)
{
    if (curIndex == numbers.Length)
    {
        var minStore = store1 <= store2 && store1 <= store3 ? store1 : store2 <=
store3 ? store2 : store3;
        var maxStore = store1 >= store2 && store1 >= store3 ? store1 : store2 >=
store3 ? store2 : store3;
        var diff = maxStore - minStore;

        if (currentMin == null) return Tuple.Create(store1, store2, store3, diff);
        if (currentMin.Item4 <= diff) return currentMin;
        return Tuple.Create(store1, store2, store3, diff); ;
    }

    var curItem = numbers[curIndex];
    var comb1 = FindMin(numbers, currentMin, curIndex + 1, store1 + curItem, store2,
store3);
    var comb2 = FindMin(numbers, currentMin, curIndex + 1, store1, store2 + curItem,
store3);
    var comb3 = FindMin(numbers, currentMin, curIndex + 1, store1, store2, store3
+ curItem);

    var min = comb1.Item4 <= comb2.Item4 && comb1.Item4 <= comb3.Item4 ? comb1 :
comb2.Item4 <= comb3.Item4 ? comb2 : comb3;
    return min;
}


Воспользоваться можно так 

var numbers = new[]{ 20, 19, 14, 13, 11, 9, 6 };
var min = FindMin(numbers, null, 0, 0, 0, 0);
Console.WriteLine($"{min.Item1} {min.Item2} {min.Item3}");


Вывод

31 32 29


Кстати, если хранить дополнительные промежуточные показатели, типа максимум/минимум
в текущей мин комбинации, то можно некоторые комбинации отсекать и не выполнять полный
перебор. 

Например, если хранить максимум в мин комбинации, и также задать начальную комбинацию
близкую к решению, то можно сэкономить на переборе и времени работы. Как пример (за
корректность не ручаюсь, но надеюсь :)):

Получим начальную комбинацию вашим алгоритмом

public Tuple GetStart(int[] numbers)
{
    int item0 = 0, item1 = 0, item2 = 0; //Кучки
    foreach (var item in numbers)
    {
        if (item0 <= item1 && item0 <= item2)
        {
            item0 += item;
        }
        else if (item1 <= item0 && item1 <= item2)
        {
            item1 += item;
        }
        else
        {
            item2 += item;
        }
    }

    var min = Math.Min(item0, Math.Min(item1, item2));
    var max = Math.Max(item0, Math.Max(item1, item2));
    return Tuple.Create(item0, item1, item2, max - min, max);
}


Улучшить эту стартовую комбинацию - означает уменьшить максимум в комбинации или
увеличить минимум. Не думаю, что будет существовать более подходящая комбинация с увеличенным
максимумом. Как это использовать? Проверять максимум в переборе

public Tuple FindMin(int[] numbers, Tuple currentMin, int curIndex, int store1, int store2, int store3)
{   
    if (curIndex == numbers.Length)
    {
        var minStore = store1 <= store2 && store1 <= store3 ? store1 : store2 <=
store3 ? store2 : store3;
        var maxStore = store1 >= store2 && store1 >= store3 ? store1 : store2 >=
store3 ? store2 : store3;
        var diff = maxStore - minStore;

        if (currentMin.Item4 <= diff) return currentMin;
        return Tuple.Create(store1, store2, store3, diff, maxStore); ;
    }

    // проверка максимума. Если ткущий максимум больше найденного, то дальше перебирать
смысла нет, так как что бы не нашли, оно будет хуже уже найденного решения. 
    if (store1 > currentMin.Item5 || store2 > currentMin.Item5 || store3 > currentMin.Item5)
return currentMin;

    var curItem = numbers[curIndex];
    var comb1 = FindMin(numbers, currentMin, curIndex + 1, store1 + curItem, store2,
store3);
    var comb2 = FindMin(numbers, currentMin, curIndex + 1, store1, store2 + curItem,
store3);
    var comb3 = FindMin(numbers, currentMin, curIndex + 1, store1, store2, store3
+ curItem);

    var min = comb1.Item4 <= comb2.Item4 && comb1.Item4 <= comb3.Item4 ? comb1 :
comb2.Item4 <= comb3.Item4 ? comb2 : comb3;
    return min;
}


Как использовать:

var numbers = new[] { 20, 19, 14, 13, 11, 9, 6 };
var start = GetStart(numbers);
var min = FindMin(numbers, start, 0, 0, 0, 0);
Console.WriteLine($"{min.Item1} {min.Item2} {min.Item3}");


Вывод аналогичен

31 32 29


В итоге, вместо 3820 итераций в первом варианте, мы получим 499 итераций. То есть
на предоставленных данных ускорение будет примерно в 7 раз.


Ответ 2

Гарантированно лучший вариант можно находить только полным перебором всех подмножеств. 
Википедия (Задача разбиения множества чисел)


Ответ 3

Полный перебор в функциональном стиле:

int[] numbers = { 20, 19, 14, 13, 11, 9, 6 };
int pilesNumber = 3;
int sum = numbers.Sum();
int combNumber = numbers.Aggregate(1, (m, number) => m * pilesNumber);
var perfectCombination =
    Enumerable.Range(0, combNumber)
              .Select(x =>
              {
                  var piles =
                      Enumerable.Range(0, pilesNumber)
                                .Select(y => new List(numbers.Length))
                                .ToArray();
                  foreach (var n in numbers)
                  {
                      piles[x % pilesNumber].Add(n);
                      x /= pilesNumber;
                  }
                  return piles;
              })
              .MinBy(piles => piles.Sum(pile => Math.Abs(pile.Sum() * pilesNumber
- sum)));
Console.WriteLine(
    string.Join("\n",
        perfectCombination.Select(
            list => list.Sum() + "=" + string.Join("+", list))));


Вывод:

29=14+9+6
31=20+11
32=19+13


Здесь MinBy из пакета Morelinq, подключите его или просто скопируйте к себе в проект
исходный код отсюда