There is an array like 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}; , you need to pack it in amounts. The fact that there is still no good is still brute-force =)

 //частоты (для [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)); }

How does it work:

  • the function f finds all combinations (there should not be a length limit, here 4), their (number of types) ^ 4, those combinations that give the required sum are selected;
  • using g, the following combinations are selected, and progress is made before it is not possible to collect the required amount;
  • the number 95 may be different if the option is better

The main difficulties with how to transfer information further - I use the vector parent to transfer, not very well. Judging by the 1st ascent to the top - debagal size 95 - variants 66 520 453 480 448 000 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 * ..)

Solution with tail 8 (45 on 118 and 2 on 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
  • 2
    en.wikipedia.org/wiki/Knapsack_problem - VladD 1:43
  • @VladD already read, I get a lot of backpacks, is it even more difficult ?, still looking in practice, I can not transfer the theory. There is something similar here, about (some) golf), there is a solution to the line, the differences ... are small? - J. Doe
  • The solution is a string by the amount of text, but this is a complete brute force, so this one line will take quite a long time. - VladD
  • The amount of 95 is not divisible. This is normal? - Qwertiy ♦
  • @Qwertiy yes, the tail will be left there, ideally one. it finds a group very quickly, it is not clear what's next. is multiplied 15 * 10 * 5 ... 200 + times. and more optimal / neopt. choose amount (95) - J. Doe

2 answers 2

Well, the simplest thing that comes to mind is to calculate the same numbers. Further, since our sum does not change, then changes of numbers occur symmetrically, for example: a + b + c = d <=> (a + n) + (bn) + c = d, that is, you need to select this n from all numbers.

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

  • one
    Plus, optimization of all sorts in the process of enumeration - for example, do not try to add numbers that are larger (95 minus the current amount), the maximum number of uses of the number can again be defined as 95 / number - markov
  • @markov It is not clear what will give, at least the code is needed, I cannot master the theory. What does it mean not to try ?, the very essence of trying is more - skipping, and the number I have is simply 4 because it is impossible so far differently and is also checked. I still try to profile. - J. Doe Nov.
  • There is an idea that f will choose the same combinations, if nothing has changed drastically (the number of elements is enough for all these options), nothing is clear .. = (, will help to discard a long train of 4-5-ok - J. Doe
  • @ J.Doe numbers necessarily go in series? - Albus Percival Dumbledore
  • @AlbusPersivalDumbledore is sorted, the order is not important. They can then be swapped in places, they are identical in size, i.e. - J. Doe

We divide this task:

1. Find possible combinations

  В нашем случае будем использовать дерево/структуру 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. Combine the combinations so that there are no extra elements in the array

  • 2 I’ll think of tomorrow, now the brains have floated)) - Albus Percival Dumbledore