Страницы

Поиск по вопросам

вторник, 2 апреля 2019 г.

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

Необходимо достичь минимальной возможной разницы между суммами значений элементов в кучках
Вот то, что получилось у меня, Принцип работы - запихивание элемента в наименьшую кучку:
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 Список по умолчанию дается не сортированным, сделаем вид, что механизм сортировки в данное коде есть, но опущен.


Ответ

Добавлю немножко динамики.
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 раз.

Комментариев нет:

Отправить комментарий