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

170
09 мая 2018, 01:52

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

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

int item0 = 0, item1 = 0, item2 = 0; //Кучки
        List<int> templist = new List<int>() { 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 Список по умолчанию дается не сортированным, сделаем вид, что механизм сортировки в данное коде есть, но опущен.

Answer 1

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

public Tuple<int, int, int, int> FindMin(int[] numbers, Tuple<int, int, int, int> 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<int, int, int ,int , int> 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<int, int, int, int, int> FindMin(int[] numbers, Tuple<int, int, int, int, int> 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 раз.

Answer 2

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

Answer 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<int>(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, подключите его или просто скопируйте к себе в проект исходный код отсюда

READ ALSO
Как реализовать Bcrypt в C#?

Как реализовать Bcrypt в C#?

Использую MD5, но слышал, что Bcrypt намного надежнее, но вот не могу найти алгоритм, как его реализовать в C#Может кто-нибудь может мне показать...

151
Найти повторяющиеся слова в тексте и посчитать количество повторений каждого из слов C#

Найти повторяющиеся слова в тексте и посчитать количество повторений каждого из слов C#

Оффтоп: я новичок, пытаюсь постигать язык программирования, но мне как самоучке это не быстро идетСуть задачи: есть текстовый файл (лог от программы,...

304
Считывание выбранного элемента из XML (XDocument)

Считывание выбранного элемента из XML (XDocument)

Какая команда в XDocument аналогична строке из xmlDocument: pictureBoxItem1ImageLocation = xmlDoc

197
Создание разного количества DropDownlist в MVC

Создание разного количества DropDownlist в MVC

Грубо говоря, есть основная запись в БД (Processing), есть коллекция - к каким темам относится основная запись (EmailTheme)Для этого написаны следующие...

172