Интересная проблема! Я выбрал другой подход для решения этой проблемы. Не знаю, элегантнее ли это, но я потратил некоторое время на размышления и хотел хотя бы поделиться своим решением.
Я делаю следующее соглашение для назначения сайта:
Индексы в массиве сайта описывают начальный индекс для значений сайта, из которого значения сайта назначаются этому сайту. Давайте сделаем это более понятным, используя два примера.
values = {2,6,3,8,2,1}
sites1 = {0,1,2}
sites2 = {0,2,5}
Два дистрибутива сайта site1 и site2 назначат значения сайта следующим образом:
дистрибутив для site1:
0: 2
1: 6
2: 3, 8, 2, 1
распределение для site2:
0: 2, 6
1: 3, 8
2: 2, 1
Таким образом, мы можем перебирать все комбинации, сдвигая индексы на сайтах вверх. В примере для 6 значений сайта мы получили бы:
{0,1,2}
{0,1,3}
{0,1,4}
{0,1,5}
{0,2,3}
{0,2,4}
{0,2,5}
{0,3,4}
{0,3,5}
{0,4,5}
{1,2,3}
{1,3,4}
{1,3,5}
.
.
.
{3,4,5}
Для всех этих распределений сайта мы суммируем значения сайта для каждого сайта, вычисляем максимальную разницу и выбираем распределение с наименьшей разницей.
Собирая все вместе, вот код, который я придумал:
#include <iostream>
#include <algorithm>
int calc_diff(int m, int n, int* values, int* sites)
{
// stores the sum of values for each site
int *result = new int[n] {0};
// iterate through all site values
for (int j = 0; j < m; j++)
{
// find the correct site index to which the value is assigned
int index = 0;
for (int i = n-1; i >= 0; i--)
{
if (j >= sites[i])
{
index = i;
break;
}
}
// sum up the site vaues
result[index] += values[j];
// debug print
// std::cout << index << ":\t" << result[index] << std::endl;
}
// print the site results
std::cout << "result:\t";
for (int i = 0; i < n; i++)
std::cout << result[i] << "\t";
// get the highest difference
auto min = std::min_element(result, result+n);
auto max = std::max_element(result, result+n);
int diff = *max - *min;
delete[] result;
return diff;
}
int main()
{
int n = 3;
int m = 6;
auto values = new int[m] {2,6,3,8,2,1};
auto sites = new int[n] {0,1,2};
// start index of the first site
int start_index = 0;
// current best difference (some really high number)
int max = 100000000;
// the current best solution
auto best = new int[n];
bool end = false;
while(!end)
{
std::cout << "sites:\t";
for (int i = 0; i < n; i++)
std::cout << sites[i] << "\t";
std::cout << std::endl;
// calculate the maximal difference of the current site distribution
auto diff = calc_diff(m, n, values, sites);
std::cout << "\nmax diff:\t" << diff << std::endl << std::endl;
// if we find a better solution than the current best, we store it as new best solution
if (diff < max)
{
max = diff;
memcpy(best, sites, n*sizeof(int));
}
// calculate new site distribution
int index = 0;
for (int i = n-1; i >= 0; i--)
{
// get the current index
index = sites[i];
// can we still move the index one position up?
// the index of the last site should not exceed m-1
// the index of all other sites should be less than the index of the next site
if ((i == n-1 && index < m-1) ||
(i < n-1 && i > 0 && index < sites[i+1]-1))
{
// increase the index of the current site
sites[i]++;
break;
}
// all site index have moved to maximum position?
// (we iterated through all indices (so i=0) and moved none of them)
if (i == 0)
{
// increase the start index of the first site
start_index++;
// reset the indices by starting from the current start_index
for (int j = 1; j < n; j++)
{
sites[j] = start_index + j;
// if we exceed the numbers of site values, we can stop the loop
if (sites[j] >= m)
end = true;
}
}
}
}
// print best soluition
std::cout << "Best distribution: ";
for (int i = 0; i < n; i++)
std::cout << best[i] << " ";
delete[] sites;
delete[] values;
delete[] best;
}