Есть массив наподобие x = {21,21,21,21,21,21,21,21,21,21,21,21,21,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,22,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,23,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,24,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,25,26,26,26,26,26,27};
, надо его упаковать по суммам.
То что есть пока еще не годно, все еще брутфорсю=)
//частоты (для [0,0,2,2] - [2,0,2])
inline auto e(std::vector<int>& z, int sz)
{
std::vector<int> c(sz, 0);
for (int i = 0; i < z.size(); i++)
c[z[i]]++;
return c;
}
inline void f(std::vector<int>& x, std::vector<int>& c, std::vector<std::vector<int>>& res, int ln)
{
#define n 4
int sz = x.size();
int d = std::pow(sz, n);
for (int i = 0; i < d; i++)
{
int sum = 0;
int j = i;
for (int i = 0; i < n; i++, j /= sz)
sum += x[j % sz];
if (sum == ln)
{
std::vector<int> _res(n); // добавил n
int j = i;
for (int i = 0; i < n; i++, j /= sz)
_res[i] = j % sz;
auto d = e(_res, sz);// count
int err = 0;
for (int i = 0; i < sz; i++)
if (d[i] > c[i])
err++;
if (!err) // пропустить те на которые нету
{
std::sort(_res.begin(), _res.end());
res.push_back(_res);
}
}
}
std::sort(res.begin(), res.end());
auto it = std::unique(res.begin(), res.end());
res.erase(it, res.end());
}
size_t best = -1;
int g(std::vector<int>& x, std::vector<int>& c, std::vector<int> parent, int depth, int ln)
{
std::vector<std::vector<int>> res;
f(x, c, res, ln);
std::random_shuffle(res.begin(), res.end()); // для разнообразия =)
#pragma omp parallel for
for (int i = 0; i < res.size(); i++)
{
auto y = x, d = c; // для каждого решения от f создается новые
// массивы с обновленной информацией
for (auto& z : res[i])
d[z]--;
for (int j = 0; j < d.size();)
{
if (!d[j])
{
y.erase(y.begin() + j);
d.erase(d.begin() + j);
}
else
j++;
}
auto _parent = parent; // результаты передаются выше,
// здесь parent - уже не нужно
for (auto& z : res[i])
_parent.push_back(x[z]);
_parent.push_back(-1);
g(y, d, _parent, depth + 1, ln);
}
/// print -->
int tail = 0, sum = 0, i = 0, l = 0;
for (auto& z : c)
tail += z;
if (best > tail)
{
best = tail, std::cout << "\ndepth = " << depth << ", tail = " << tail << '\n';
for (auto& z : parent)
{
if (z == -1)
std::cout << " = " << sum << std::endl, sum = i = 0, l++;
else
{
if (!i++)
std::cout << l << ": ";
std::cout << z << '+', sum += z;
}
}
std::cout << '\n';
for (int i = 0; i < c.size(); i++)
while (c[i]--)
std::cout << x[i] << '+';
}
return tail;
}
void main(int argc, char **argv)
{
std::vector<int> c(x.back() - x.front() + 1, 0);
for (int i = 0; i < x.size(); i++)
c[x[i] - x.front()]++;
auto it = std::unique(x.begin(), x.end());
x.erase(it, x.end());
std::vector<int> res;
g(x, c, res, 0, strtoul(argv[1], 0, 10));
}
Как работает:
- функция f находит все сочетания (ограничения длины не должно быть, здесь 4), их (кол-во типов)^4, выбираются те сочетания, которые дают нужную сумму;
- при помощи g выбираются следующие сочетания, и идет продвижение до того как не будет возможности собрать нужную сумму;
- число 95 может быть другим, если вариант получится лучше
Основные сложности с тем как передать информацию дальше - я использую вектор parent чтобы передавать, не очень удачно.
Судя по 1-му восхождению на вершину - дебагал размер 95 - вариантов 66520
453480
448000
000`000
(=16*11*11*5*5*5*5*5*5*5*5*5*4*4*4*4* 4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*4*1*..)
Решение с хвостом 8 (45 по 118 и 2 по 101):
21+21+23+26+27 21+21+24+26+26 21+22+25+25+25 21+23+24+25+25 21+22+25+25+25 21+24+24+24+25 21+24+24+24+25 21+24+24+24+25 21+24+24+24+25 21+22+25+25+25 21+22+25+25+25 22+22+24+25+25 22+22+24+25+25 22+22+24+25+25 22+22+24+25+25 22+22+24+25+25 22+22+24+25+25 22+22+24+25+25 22+22+24+25+25 22+22+24+25+25 22+22+24+25+25 22+22+24+25+25 22+22+24+25+25 22+22+24+25+25 22+23+23+25+25 23+23+23+24+25 23+23+23+24+25 23+23+23+24+25 23+23+23+24+25 23+23+23+24+25 23+23+23+24+25 23+23+23+24+25 23+23+23+24+25 23+23+23+24+25 23+23+23+24+25 23+23+24+24+24 23+23+24+24+24 23+23+24+24+24 23+23+24+24+24 23+23+24+24+24 23+23+24+24+24 23+23+24+24+24 23+23+24+24+24 23+23+24+24+24 23+23+24+24+24 25+25+25+26 25+25+25+26