Необходимо достичь минимальной возможной разницы между суммами значений элементов в кучках
Вот то, что получилось у меня, Принцип работы - запихивание элемента в наименьшую кучку:
int item0 = 0, item1 = 0, item2 = 0; //Кучки
List
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
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
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
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 раз.
Комментариев нет:
Отправить комментарий