Необходимо достичь минимальной возможной разницы между суммами значений элементов в кучках
Вот то, что получилось у меня, Принцип работы - запихивание элемента в наименьшую кучку:
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 Список по умолчанию дается не сортированным, сделаем вид, что механизм сортировки в данное коде есть, но опущен.
Добавлю немножко динамики.
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 раз.
Гарантированно лучший вариант можно находить только полным перебором всех подмножеств. Википедия (Задача разбиения множества чисел)
Полный перебор в функциональном стиле:
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
, подключите его или просто скопируйте к себе в проект исходный код отсюда
Кофе для программистов: как напиток влияет на продуктивность кодеров?
Рекламные вывески: как привлечь внимание и увеличить продажи
Стратегії та тренди в SMM - Технології, що формують майбутнє сьогодні
Выделенный сервер, что это, для чего нужен и какие характеристики важны?
Современные решения для бизнеса: как облачные и виртуальные технологии меняют рынок
Использую MD5, но слышал, что Bcrypt намного надежнее, но вот не могу найти алгоритм, как его реализовать в C#Может кто-нибудь может мне показать...
Оффтоп: я новичок, пытаюсь постигать язык программирования, но мне как самоучке это не быстро идетСуть задачи: есть текстовый файл (лог от программы,...
Какая команда в XDocument аналогична строке из xmlDocument: pictureBoxItem1ImageLocation = xmlDoc
Грубо говоря, есть основная запись в БД (Processing), есть коллекция - к каким темам относится основная запись (EmailTheme)Для этого написаны следующие...