0

Есть массив наподобие 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 - вариантов 66520453480448000000`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
7
  • 2
    en.wikipedia.org/wiki/Knapsack_problem
    – VladD
    3 ноя 2016 в 13:43
  • @VladD уже читал, у меня получается много рюкзаков, это еще сложнее?, все-таки ищу на практике, теорию не смогу перенести. Здесь что-то похожее есть, про (какой-то) гольф), там решение в строку, отличия... небольшие?
    – J. Doe
    3 ноя 2016 в 13:55
  • Решение в строку по количеству текста, но это полный перебор, так что эта одна строка будет считать довольно долго.
    – VladD
    3 ноя 2016 в 14:00
  • Сумма на 95 не делится. Это нормально?
    – Qwertiy
    3 ноя 2016 в 14:53
  • @Qwertiy да, там хвост отстанется, в идеале один. находит группу оно очень быстро, непонятно что дальше. идет умножение 15*10*5... 200+раз. и еще оптимально/неопт. выбрать сумму (95)
    – J. Doe
    3 ноя 2016 в 14:58

2 ответа 2

3

Ну самое простое что приходит в голову - это подсчитать одинаковые числа. Дальше так как у нас сумма остаётся не изменой, то и изменения чисел происходит симметрично например: a+b+c=d <=> (a+n)+(b-n)+c=d, то бишь надо выделить эту самую n из всех чисел.

Итого: массив<КоличествоПовторений,n \\относительно одного(возможно выдуманного) числа>

5
  • 1
    Плюс оптимизация всяких в процессе переборов - например не пробовать добавлять числа, которые больше (95 минус текущая сумма), максимальное кол-во использований числа опять же можно определить как 95/число
    – markov
    3 ноя 2016 в 15:12
  • @markov Не понятно что даст, код хотя бы нужен, теорию не осилю. Что значит не пробовать?, сама суть пробовать - больше - пропуск, и кол-во у меня просто 4 т.к невозможно пока что по-другому и тоже проверяется. Я еще попытають попрофилировать.
    – J. Doe
    3 ноя 2016 в 15:22
  • Есть идея что f будет выбирать одинаковые комбинации, если ничего кардинально не поменялось (кол-ва элементов хватает на все эти варианты), ничего не понятно..=( ,поможет отбросить длинную череду 4-5-ок
    – J. Doe
    3 ноя 2016 в 15:35
  • @J.Doe числа обязательно идут последовательно? 3 ноя 2016 в 15:51
  • @АльбусПерсивальДамблдор это отсортированный, порядок не важен. Их можно потом местами поменять, они идентичные по размеру т.е
    – J. Doe
    3 ноя 2016 в 15:56
0

Подразделим эту задачу:

1. Найти возможные комбинации

 В нашем случае будем использовать дерево/структуру Node:
 int Parent;
 int value;
 int Nodes[];

 Общие данные:
 int variants[]; \\варианты подставляемых чисел, отсортированы по возрастанию
 int counts[]; \\количество одинаковых/повторяющихся вариантов
 int finish; \\число к которому стремимся/надо найти

 И рекурсивный метод:
 int Find(ushort part, Node nd)\\остаток которого не хватает до конечного числа & ветвь
 {
     for(int n = 0; n < variants[].Count; n++)
     {
         int temp = finish - variants[n];
         if(temp == 0)
         {
             \\Подходящий вариант
             nd.Nodes += new Node(){ value = variants[n]; parent nd; }.ToString()
         }
         else if(temp > variants[].First()) \\если ещё можно подставить числа
         {
             \\Надо углублять дерево
             Find(temp,
             new Node(){ value = variants[n]; parent = nd; }
             );
         }
     }
 }

 Метод превращающий структуру в текст:\\если лень самому придумывать
 string Node.ToString()
 {
     Node temp = this;
     while(Parent != null)
     {
        temp.value.ToString() + " ";\\Int32 в строку
        temp = Parent;
     }
 }

2. Совместить комбинации, чтоб не осталось лишних элементов в массиве

1

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.