@epitxx

Алгоритм максимально равномерного распределения предметов?

Допустим есть несколько списков каких-либо предметов, и еще один дополнительный список источник из которого они будут пополняться.
Все списки характеризуются целыми числами, которые обозначают количество предметов в них.
Нужно составить алгоритм на вход которому подается список числа предметов, и число предметов в источнике, а на выходе получается список с оптимизированным количеством предметов.
Думаю на примерах будет более понятно:
[30, 50, 350], 300 -> [190, 190, 350]
[30, 50, 350], 1001 -> [477, 477, 477]

Алгоритм желательно привести на каком-нибудь языков программирования.
  • Вопрос задан
  • 133 просмотра
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
std::vector<int> DistributeExtraObjectsFairly(std::vector<int> objects, int extra_objects) {
    std::vector<int> permutation;
    permutation.reserve(objects.size()+1);
    permutation.resize(objects.size());
    std::iota(permutation.begin(), permutation.end(), 0);
    std::sort(permutation.begin(), permutation.end(),
        [&objects](const int &a, const int &b) {return objects[a] < objects[b];});
    int num_increased = 1;
    permutation.push_back(0);
    int step = (objects[permutation[num_increased]] - objects[permutation[num_increased-1]]) * num_increased;
    while (extra_objects >= step && num_increased < objects.size()) {
        extra_objects -= step;
        ++num_increased;
        step = (objects[permutation[num_increased]] - objects[permutation[num_increased-1]]) * num_increased; 
    }
    int final_value = objects[permutation[num_increased-1]] + extra_objects / num_increased;
    int num_bigger_values = extra_objects % num_increased;
    for (int i = 0; i < num_bigger_values; ++i) {
        objects[permutation[i]] = final_value + 1;
    }
    for (int i = num_bigger_values; i < num_increased; ++i) {
        objects[permutation[i]] = final_value;
    }
    return objects;
}


Идея: отсортировать числа и добавлять к минимальному, пока оно не станет равно следующему. Потом добавлять к двум мнимальным. Потом к трем и т.д. Вместо добавления к каждому числу индивидуально по одному объекту считаем, сколько надо объектов чтобы первые несколько первых стали равны следующему. Когда нашли, что дальше не приравнять - распределяем остаток среди затронутых элементов по-ровну, остатки кидая куда-то.

Есть еще хак с добавлением лишнего 0 в массив перестановки для того, чтобы не разбирать лишний случай в цикле и не считать два раза одно и то же.

Edit: работает за O(n log n), где n - количество элементов в списке. Быстрее, я подозреваю, никак. Есть еще решение за O(n log M) - где М - максимально возможное число во входных данных. Это через бинпоиск по минимальному числу в конце.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 2
@rPman
Сортируешь числа в списке предметов по возрастанию
Алгоритм добавления количества Z следующий:
* по очереди берешь равные по значению числа (пусть будет X, количество N) и следующий за ними не равный по значению (пусть будет Y), если такого нет то считаем это значение - бесконечным
* вычисляешь разницу Y-X, вычисляем, сколько можно дололжить к ним от Z - считаем если (Y-X)*N меньше или равно Z значит заменяем N первых чисел на Y, а из Z вычитаем (Y-X)*N, если (Y-X)*N больше Z (в т.ч. если Y - бесконечность) значит к этим первым N числам из списка прибавляем Z/N (если не делится на цело, значит берем целую часть от Z а затем остаток по 1 докидываем вторым проходом, Z обнуляем, завершаем работу алгоритма
* если Z не ноль, повторяем весь алгоритм
Ответ написан
Комментировать
sergiks
@sergiks Куратор тега Алгоритмы
♬♬
Расставить начальные значения на оси.
Значение указывает на одно или больше «ведёрок» из начального массива, которые надо наполнять.
Двигаться слева направо, накапливая «вёдра», в которые льём.

На каждом шаге известно, сколько осталось запаса для разлива.
Есть «ёмкость» шага – кол-во вёдер умноженное на длину текущего шага.
Пока запас выше или равен ёмкости – добавляем в текущие вёдра поровну и к следующему шагу.
Потом, если что-то осталось – разделить поровну, округлив в бОльшую сторону, и по очереди раздавать по актуальным ведёркам.
JavaScript
далеко не оптимальный код, но, вроде, рабочий
function spread(arr, src) {
  const result = [...arr]; // копия исходного массива
  if (src <= 0) return result;

  const axis = {}; // value: [ids of bins]
  arr.forEach((v, i) => {
    if (!axis[v]) axis[v] = [];
    axis[v].push(i);
  });

  const keys = Object.keys(axis).sort((a, b) => a - b);

  const bins = [...axis[keys[0]]]; // ids of "bins" we're filling
  for (let i = 1; i < keys.length; i++) {
    const currentKey = keys[i];
    const prevKey = keys[i - 1];
    const diff = currentKey - prevKey;
    const capacity = bins.length * diff;
    
    if (src < capacity) break;

    bins.forEach(key => result[key] += diff);
    src -= capacity;
    bins.push(...axis[currentKey]);
  }

  if (src) {
    const want = Math.ceil(src / bins.length);
    bins.forEach(key => {
      const given = Math.min(src, want)
      result[key] += given;
      src -= given;
    });
  }

  console.log(result);
  return result;
}

spread([30, 50, 350], 300); // [ 190, 190, 350 ]
spread([30, 50, 350], 1001); // [ 477, 477, 477 ]
spread([130, 50, 50, 101], 800); // [ 282, 283, 283, 283 ]
Ответ написан
Ваш ответ на вопрос

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

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