Не знал, как подступиться к проблеме, но благодаря вашим советам решил задачу, по крайней мере, полным перебором :) Спасибо!
Правда, явно требуется оптимизация, т.к. если цилиндров 9, уже начинает тормозить. Но как вклинить хотя бы один из советов
Boris Korobkov...
// факториал числа $n - кол-во перестановок элементов массива
function factorial($n) {
if ($n <= 1)
return 1;
return $n * factorial($n - 1);
}
// возвращает перестановку элементов в массиве по ее порядковому номеру (код Лехмера)
function permutation($arr, $arr_keys, $arr_size, $index) {
for ($i = 0; $i < $arr_size; $i ++) {
$item = $index % ($arr_size - $i);
$index = floor($index / ($arr_size - $i));
$permutation[$arr_keys[$item]] = $arr[$item];
array_splice($arr, $item, 1);
array_splice($arr_keys, $item, 1);
}
return $permutation;
}
// распределение элементов по группам
function divide_into_groups($num_groups, $arr, $arr_size, $ideal_height) {
$arr_keys = array_keys($arr); // для сохранения ключей
$arr = array_combine(range(0, $arr_size - 1), $arr); // переводим ключи в числа по порядку для оптимизации цикла ниже: "for ($j = $start..."
$groups = []; // многомерный массив распределения элементов по группам
$heights = []; // высоты групп
$start = 0;
for ($i = 0; $i < $num_groups; $i ++) { // перебираем группы
for ($j = $start; $j < $arr_size; $j ++) { // перебираем элементы
$start = $j + 1; // последний перебранный элемент
$groups[$i][$arr_keys[$j]] = $arr[$j]; // дополняем многомерный массив
$heights[$i] = !isset($heights[$i]) ? $arr[$j] : $heights[$i] + $arr[$j]; // увеличиваем высоту группы
if ($heights[$i] >= $ideal_height) // достигли ИМВВ, идём в следующую группу
break;
}
}
return [$groups, max($heights)];
}
$num_groups = 3; // кол-во групп
$arr = array(100, 110, 150, 160, 180, 185, 200, 205, 300); // высоты (просто из головы)
$arr_keys = array_keys($arr); // вспомогательный массив для сохранения ключей
$arr_size = count($arr); // длина массива
$num_variants = factorial($arr_size); // количество перестановок элементов массива
$ideal_height = max(array_sum($arr) / $num_groups, max($arr), min($arr)); // ИМВВ
$min_groups_height = array_sum($arr); // минимально возможная общая высота групп (начинаем просто с суммарной высоты всех элементов)
$optimal_variant = []; // оптимальный вариант распределения по группам
for ($i = 0; $i < $num_variants; $i ++) {
// очередная перестановка элементов в массиве
$permutation = permutation($arr, $arr_keys, $arr_size, $i);
// распределение элементов по группам
list($groups_arr, $groups_height) = divide_into_groups($num_groups, $permutation, $arr_size, $ideal_height);
// если этот вариант лучше других, сохраняем его в качестве оптимального на текущий момент
if ($min_groups_height > $groups_height) {
$min_groups_height = $groups_height;
$optimal_variant = $groups_arr;
}
}
echo 'ИМВВ - '.$ideal_height.'<br /><br />';
echo 'Оптимальный вариант распределения элементов: <pre>'.print_r($optimal_variant, true).'</pre>';
echo 'Минимально возможная общая высота групп - '.$min_groups_height;
