@russeljo

Какой алгоритм можно применить для задачи размещения числа в фиксированные контейнеры?

Подскажите на что похожа эта задача, как её можно решить. Язык php.

Насос собирается из секций. Сам насос содержит в себе ступени насоса - это число N.
Например у нас есть N=300 ступеней в насосе.
Есть контейнеры:
длина,м _______ макс. количество ступеней в контейнере
3,0 ________ 95
3,5 ________ 111
4,0 ________ 127
4,5 ________ 144
5,0 ________ 160
5,5 ________ 177
6,0 ________ 193

В одну секцию(контейнер) можно положить по максимуму, но можно и не полностью(ставятся заглушки).
Для данного примера, результат можно записать так "4,5 + 5,0"=9,5 метров, т.е. мы 300 ступеней раскидали по 2 контейнера 144+160 = 304, соответственно в одном из контейнеров будет 4 заглушки.
Но слишком много заглушек - это очень плохо, поэтому их не более 20% от макс.количества в секции.

Могут быть еще варианты "4,0 + 5,5"=9,5 метров, 127+177=304ступеней.
Или еще такой "3,0 + 3,5 + 3,5"=10м

Соответственно, лучший вариант - это минимальная длина и минимум секций.
  • Вопрос задан
  • 147 просмотров
Пригласить эксперта
Ответы на вопрос 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Ваша задача очень похожа на задачу о рюкзаке.

Во первых, можно забыть про заглушки, если требовать собрать ровно от 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)
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы