Ваша задача очень похожа на задачу о рюкзаке.
Во первых, можно забыть про заглушки, если требовать собрать ровно от N до 1.25N секций.
Т.е. в вашем примере вам можно собрать от 300 до 400 секций.
Теперь ваша задача в точности становится задачей о рюкзаке, количество секций в контейнере - это "длина" вещи из задачи о рюкзаке, а длина - это "цена".
И вам надо, как в задаче о рюкзаке, набрать каких-то "вещей", т.ч. рюкзак заполнен от 300 до 400 и суммарная "цена" минимальна.
Если контейнеров не много (до 20-25), то можно решать полным перебором: рекурсивной функцией перебираете сколько контейнеров каждого типа вы берете в ответ. Если суммарное количество секций выше 1.25N, то останавливаетесь. В конце, когда перебрали все контейнеры, если набрали от N до 1.25N секций, то сравниваете текущую длину с оптимальным ответом и запоминаете, если длина меньше.
Довольно быстрое решение - через динамическое программирование. Заведите массив от 0 до 1.25N. В нем будет хранится минимально возможная длина для набора контейнеров с заданным количеством секций. Изначально заполните его -1, а в индекс [0] положите 0.0.
Теперь для каждого контейнера пройдитесь по массиву слева направо и, если текущая длина неотрицательна, то попробуйте приложить текущую секцию к набору, добавив количество секций к индексу, а длину к значению массива. Если по новому индексу лежит что-то хуже, чем то что вы насчитали, перезапишите это значение. Я php не знаю, вот вам решение на C++.
// 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;
}
}
Лучше, все-таки, если вы сможете задать длины целыми числами, например, в миллиметрах. Тогда не будет проблем с точностью. Это слегка адаптированный под вашу задачу стандартный алгоритм динамического программирования для задачи о рюкзаке. Погуглите, почитайте википедию. Там еще указаны различные аппроксимационные алгоритмы. Если у вас ОЧЕНЬ много секций (N>10^8) и данный алгоритм требует слишком много памяти, но вам пойдет и достаточно хорошее решение, пусть и не оптимальное, то используйте аппроксимационные алгоритмы.
Если хотите изменить допустимые проценты заглушек - меняйте коэффициент 5/4 в коде.
Важно: это решение предполагает, что все контейнеры допускают одинаковый процент заглушек.
Решение уже ищет минимальное количество заглушек при минимально возможной общей длине.
Edit: исправил код восстановления ответа - сначала забыл разобрать случай недостижимых состояний (-1 в массиве length)
