<?
set_time_limit(0);
function square ($n) {
// возведение числа $n в квадрат
return $n*$n;
}
function array_avg ($arr) {
// вычисление среднего арифметического
return array_sum($arr)/count($arr);
}
function dispersion ($arr) {
// вычисление дисперсии
$avg_x = array_avg($arr);
$avg_x2 = array_avg(array_map("square", $arr));
return $avg_x2 - square($avg_x);
}
function groups_sum ($arr, $partition) {
/*
вычисление сумм элементов каждой группы
$arr - исходный массив
$partition - разбиение массива на группы; это массив, в котором записано кол-во элементов для каждой группы
Например, $partition = array(2,2,1) - это описание разбиения массива из 5-ти элементов на 3 группы:
2 элемента + 2 элемента + 1 элемент
*/
$g_sum = array(); // массив сумм элементов каждой группы
$offset = 0;
foreach ($partition as $group_len) {
$g_sum[] = array_sum(array_slice($arr, $offset, $group_len));
$offset += $group_len;
}
return $g_sum;
}
function next_partition ($partition) {
// получение следующего разбиения массива
$count = count($partition);
// начиная с предпоследнего элемента ищем самый правый элемент не равный 1
$i_not_1 = FALSE;
for ($i=$count-2; $i>=0; $i--) {
if ($partition[$i]>1) {
$i_not_1 = $i;
break;
}
}
if ($i_not_1===FALSE)
return FALSE;
else {
$partition[$i_not_1]--;
if ($i_not_1 < $count-2) {
// если единица перебрасывается не в последний элемент массива
$partition[$i_not_1+1] += $partition[$count-1];
for ($i=$i_not_1+2; $i<$count; $i++)
$partition[$i] = 1;
}
else
$partition[$i_not_1+1]++;
return $partition;
}
}
// ------------------------------
// исходные данные
$arr = array(
748, 285, 4, 1, 1, 2, 596, 257, 115, 601,
25, 228, 129, 185, 206, 13, 82, 2125, 1226, 3256,
12, 211, 17, 439, 1694, 133, 105, 103, 116, 28,
141, 113
);
$s_min = 100; // минимально допустимая сумма элементов группы
$s_max = 3500; // максимально допустимая сумма элементов группы
$num_groups_min = 1; // минимально допустимое кол-во групп
$num_groups_max = 7; // максимально допустимое кол-во групп
// ------------------------------
$disp_min = NULL; // минимальная дисперсия
$partition_best = NULL; // разбиение массива, при котором достигается минимальная дисперсия
$arr_size = count($arr);
$t1 = microtime(1); // засекаем время
// перебираем допустимые $num_groups (кол-во групп, на которые разбивается массив)
for ($num_groups=$num_groups_min; $num_groups<=$num_groups_max; $num_groups++) {
$partition = array_fill(0,$num_groups,1);
$partition[0] = $arr_size - $num_groups + 1;
// перебираем все разбиения массива $arr на $num_groups групп
do {
$g_sum = groups_sum($arr, $partition);
if (min($g_sum)>=$s_min && max($g_sum)<=$s_max) {
$disp = dispersion($g_sum);
if (!$partition_best || $disp<$disp_min) {
$disp_min = $disp;
$partition_best = $partition;
}
}
} while ($partition = next_partition($partition));
}
$t = round(microtime(1)-$t1, 2); // вычисляем время перебора
$offset = 0;
$group_id = 1;
foreach ($partition_best as $group_len) {
$slice = array_slice($arr, $offset, $group_len);
$groups[$group_id]["slice"] = $slice;
$groups[$group_id]["sum"] = array_sum($slice);
$groups[$group_id]["num"] = count($slice);
$offset += $group_len;
$group_id++;
}
// выводим результат
print("<style>
table {border-collapse: collapse; font: 12px verdana}
th {background: #ddd}
th, td {border: 1px solid black; padding: 5px 10px}
</style>");
print("<table><tr><th>№ группы</th><th>Группа</th><th>Сумма элементов</th><th>Кол-во элементов</th></tr>");
foreach ($groups as $group_id => $group)
print("<tr><td>{$group_id}</td><td>".implode(", ",$group["slice"])."</td><td>{$group["sum"]}</td><td>{$group["num"]}</td></tr>");
print("<tr><td colspan=4><b>Дисперсия:</b> {$disp_min}</td></tr>");
print("<tr><td colspan=4><b>Время выполнения:</b> {$t} сек.</td></tr>");
print("</table>");
?>
.
