What algorithm can be applied to the problem of placing a number in fixed containers?

Question

PHP

Please let me know what this problem looks like and how it can be solved. php language.

The pump is assembled in sections. The pump itself contains the pump stages - this is the number N.
For example, we have N = 300 stages in the pump.
There are containers:
length, m _______ max. number of steps in the container
3.0 ________ 95
3.5 ________ 111
​​4.0 ________ 127
4.5 ________ 144
5.0 ________ 160
5.5 ________ 177 6.0 ________
193

but it is possible and not completely (stubs are placed).
For this example, the result can be written as "4.5 + 5.0" = 9.5 meters, i.e. we scattered 300 steps in 2 containers 144 + 160 = 304, respectively, in one of the containers there will be 4 stubs.
But too many stubs are very bad, so there are no more than 20% of the maximum number in the section.

There may be more options "4.0 + 5.5" = 9.5 meters, 127 + 177 = 304 steps.
Or another such "3.0 + 3.5 + 3.5" = 10m

Accordingly, the best option is the minimum length and minimum sections.

Answer 1

Your problem is very similar to the knapsack problem.
Firstly, you can forget about the stubs if you require to collect exactly from N to 1.25N sections.
Those. in your example, you can collect from 300 to 400 sections.
Now your problem becomes exactly the knapsack problem, the number of sections in the container is the "length" of the thing from the knapsack problem, and the length is the "price".
And you need, as in the knapsack problem, to collect some "things", incl. the backpack is filled from 300 to 400 and the total "price" is minimal.
If there are not many containers (up to 20-25), then you can solve by exhaustive enumeration: using a recursive function, iterate over how many containers of each type you take in response. If the total number of sections is above 1.25N, then stop. At the end, when all the containers have been sorted out, if you have collected from N to 1.25N sections, then you compare the current length with the optimal answer and remember if the length is less.
A fairly quick solution is through dynamic programming. Get an array from 0 to 1.25N. It will store the minimum possible length for a set of containers with a given number of sections. Initially fill it with -1, and put 0.0 in index [0].
Now, for each container, iterate through the array from left to right, and if the current length is non-negative, then try to append the current section to the set, adding the number of sections to the index and the length to the array value. If the new index contains something worse than what you counted, overwrite this value. I don't know php, here's a C++ solution for you.

// Container - структура содержащая длину length и количество секций sections.
int maxn = n*5/4; // Округленное вниз целое число.
vector<float> length(maxn+1, -1.0);
length[0] = 0.0;
vector<container> best(maxn+1);
for (Container c: containers) {
  for(int i = 0; i < maxn; ++i) {
    if (length[i] < 0) continue;
    int j = i + с.sections;
    if (j <= maxn && (length[j] < 0 || length[j] > length[i] + c.length)) {
      length[j] = length[i] + c.length;
      best[j] = c;
    }
  }
}
int besti = -1;
float bestlen = 100000000;
for (int i = n; i <= maxn; ++i) {
  if (length[i] > 0 &&  length[i] < bestlen) {
    besti = i;
    bestlen = length[i];
  }
}
if (besti == -1) {
  cout << "Нет решения" << endl;
} else {
  cout << "Минимально возможная длина: " << length[besti] << endl;
  cout << "Контейнеры:" << endl;
  while (besti > 0) {
    cout << best[besti].length << endl;
    besti -= best[besti].sections;
  }
}

It's better, after all, if you can specify the lengths as integers, for example, in millimeters. Then there will be no problems with accuracy. This is a standard dynamic programming algorithm for the knapsack problem slightly adapted to your problem. Google it, read Wikipedia. Various approximation algorithms are also indicated there. If you have VERY many partitions (N>10^8) and this algorithm requires too much memory, but you can use a good enough solution, albeit not optimal, then use approximation algorithms.
If you want to change the allowable percentage of stubs - change the coefficient 5/4 in the code.
Important: This solution assumes that all containers allow the same percentage of stubs.
The solution is already looking for the minimum number of stubs at the minimum possible total length.
Edit: fixed response recovery code - first forgot to parse case of unreachable states (-1 in length array)