Задача равномерного распределения

@svrn · Регистрация: 22.03.2019

Author24 — интернет-сервис помощи студентам

Здравствуйте, нужна помощь с поиском подходов к решению.

Формально задачу можно сформулировать так: Дано множество разноцветных шаров (один шар - один цвет), и несколько корзин, для которых обозначено какие цвета можно в эти корзины класть (одна корзина - от одного цвета и больше). Необходимо разложить шары по корзинам так, чтобы кол-во шаров в корзине было равным насколько это возможно.

@vantfiles · 22.03.2019, 14:23

в корзинЕ или в корзинАХ ?

@svrn · 25.03.2019, 10:32 **[ТС]**

В корзинах. Я пришел к следующему алгоритму: представить всё в виде двудольного графа, где первая доля - множество шаров, вторая доля - множество корзин, ребро - гарантия что шар подходит к корзине. первую долю отсортировать по величине степени вершин по возрастанию, т.е. самые редкие и невостребованные цвета будут распределятся первыми; вторую долю отсортировать по степени вершин по убыванию, т.е. корзины с бОльшим количеством принимаемых цветов в верху.

После построения графа и сортировки идём по первой доле и распределяем шары, при этом запоминая в какую корзину положили последний шар, и когда начинаем распределять следующий шар, то корзину для него ищем начиная с текущей корзины в памяти. Это даст нам равномерное распределение шаров одного цвета по корзинам, которые этот цвет принимают, но естественно не гарантирует равного кол-ва шаров во всех корзинах. Над этим ещё думаю.

@svrn · 25.03.2019, 19:08 **[ТС]**

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

Пытаюсь пока искать методы и реализации. Но не до конца уверен что в качестве стоимости можно использовать функции.

@Дмитррр · 27.03.2019, 21:29

Ты бы задачу сформулировал более чётко. Ответ-то, думаю простой найдётся.

Сообщение от svrn

Дано множество разноцветных шаров

Конечное или бесконечное?
Вероятность или количество каждого конкретного цвета известно или нет?

Сообщение от svrn

какие цвета можно в эти корзины класть

В любой пропорции?

Сообщение от svrn

кол-во шаров в корзине было равным

Только по количеству и всё?
Если шаров конечное количество, то их надо разместить все?

@svrn · 28.03.2019, 22:59 **[ТС]**

Пытался на скорую руку формализовать задачу.
Итак, дано конечное количество разноцветных шаров, цвет каждого шара известен заранее. Дано некоторое количество корзин, принимающих один или несколько цветов. Задача разместить шары в корзинах максимально равномерно по количеству, без пропорций и каких либо доп. критериев. Для условности можно считать что для каждого шара есть корзина принимающая его цвет.

По факту это классическая задача о назначениях, в которой работнику можно назначить несколько работ, и нужно равномерно распределить работы среди работников. При этом считаем что время выполнения любой работы константа.

@Дмитррр · 29.03.2019, 12:50

Остался вопрос (№1): шары нужно все использовать или не все?
Если не все, то сколько нужно. Если любое количество, то положил в каждую корзину по одному шару и задача выполнена.
А если нужны все, то равномерность абсолютно не гарантирована. Например, синих шаров 100, а синяя корзина одна; красных шаров 3, а корзин 5.

И ещё вопрос (№2): нужно ли использовать каждый цвет шара? Если у меня белая корзина и чёрно-белая, то могу её заполнить только белыми шарами, забив на чёрные?

Но в любом случае подход должен быть примерно таким:
1. посчитать количество шаров каждого цвета и корзин каждого цвета;
2. Дальше надо понять какое количество шаров надо в корзины
- для одноцветных корзин просто: соотношение количества определённых шаров к количеству таких же одноцветных корзин. Это будет максимум заполнения всех корзин.
- для многоцветных вот самое сложное. Нужна пирамидка условий... Например, есть шары шА и шБ. И корзины кА, кБ и кАБ. Если шА меньше чем шБ в 2 и более раз, то всё понятно: Все шА в кА, а шБ в кБ и кАБ. Если разница меньше, чем в 2 раза , то надо считать пропорцию. (шА+шБ)/(кА+кБ+кАБ). Это и будет количество шаров в корзинах. Но если корзин больше, то придётся перебирать много условий. Но тут важно понять, что однозначного распределение шаров может не быть.
3. далее собственно можно начать заполнять корзины до нужного количества. Начать лучше с того цвета, который дал ограничение, т.к. остальных есть с запасом. Последовательность заполнения в общем случае произвольная, если нет никаких дополнительных ограничений (например, на основе моего второго вопроса в этом сообщении).

Есть другой вариант. последовательное заполнение.
1. Берём случайный шар и кладём в случайную подходящую корзину.
2. Берём следующий отличный от первого и кладём в отличную от первой корзину.
3. Так перебираем все цвета шаров складируя во все корзины по порядку.
4. Если очередной взятый шар нельзя положить в корзину так, чтобы разница шаров в корзинах не превышала единицу, то берём шар другого цвета.
5. Если попробовав все цвета шаров ни один не подошёл, то для надо берём опять все шары поочереди и не просто пробуем положить в очередную корзину, а ещё рассматриваем перенос/обмен шаров между многоцветными корзинами.

@svrn · 29.03.2019, 13:29 **[ТС]**

ответ на вопрос №1: Шары нужно использовать все по максимуму.
ответ на вопрос №2: При распределении нужно учитывать только основное требование равномерного распределения.

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

Ориентировочно можно думать о 100 000 шаров и 1000 корзин, и 256 цветах.

Второй вариант это по сути и есть алгоритм поиска максимального потока минимальной стоимости, просто описан довольно формально. Там мы тоже сначала раскидываем шары по максимуму, а потом пытаемся перекладывать, что бы "удешевить" нахождение шара в корзине. Соответственно если стоимость укладки шара в корзину равна скажем кол-ву шаров в корзине +1, то по идее алгоритм должен максимально равномерно разложить шары в многоцветных корзинах и при этом максимально заполнить "предельные" корзины (100 зеленых шаров и только 1 зеленая корзина).

Я нашел похожую задачу в семинаре для первого курса какого то ВУЗа, и поэтому мне подумалось, что задача довольно распространенная и простая. Хотя гугление не дало мне практически никаких результатов.

@Ygg · 29.03.2019, 16:39

Исписал пару листочков и родил такой алгоритм:
На каждом шаге алгоритма выбираем корзину, выбираем для неё шар, кладём выбранный шар в выбранную корзину. Повторяем пока не закончатся все шары.
1) Исключаем корзины, в которые ничего нельзя положить.
2) Из оставшихся выбираем корзину, в которой меньше всего шаров.
3) Если таких корзин несколько, то выбираем такую, для которой количество возможных шаров минимально.

Пояснение к пункту 3

Пусть у нас есть N красных и M чёрных шаров. И все эти цвета могут быть положены в корзину. Тогда максимальное количество шаров в корзине будет равно (N+M). Для каждой корзины можно найти свой максимум. Нам нужна корзина, максимум которой самый маленький из всех. При этом, на каждом шаге алгоритма один из шаров будет оказываться в какой-то корзине. Поэтому максимумы будут постоянно меняться. Кроме того, если в корзине уже лежит какое-то количество шаров, то их нужно приплюсовать к максимуму возможных.

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

На двух примерах вроде работает. На большее количество тестов меня не хватило.

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

Код

Вариант 1
Цветные шары           Корзины

  /---\                +-----+
 /     \               |     |
 |  4  |  ---------->  |     |
 \     /      ------>  |     |
  \---/      /         +-----+
            /
  /---\    /           +-----+
 /     \  /            |     |
 |  6  |  ---------->  |     |
 \     /               |     |
  \---/                +-----+




Вариант 2
Цветные шары           Корзины

  /---\                +-----+
 /     \               |     |
 |  5  |  ---------->  |     |
 \     /  \            |     |
  \---/    \           +-----+
            \
             \         +-----+
              ------>  |     |
                       |     |
              ------>  |     |
             /         +-----+
            /
  /---\    /           +-----+
 /     \  /            |     |
 |  6  |  ---------->  |     |
 \     /               |     |
  \---/                +-----+

@svrn · 02.04.2019, 17:27 **[ТС]**

Ygg, скорее всего это самый приемлемый алгоритм. Мне правда он показался довольно перегруженным поиском минимумом/максимов. Я решил делать следующим образом:

1) сначала формируем матрицу смежности шаров/корзин. Будем считать что для каждого шара есть корзина, и наоборот.
2) в отдельном массиве считаем сколько шаров в какой корзине лежит. То есть просто счетчик количества шаров в корзине.
3) бежим по матрице смежности по шарам.
3.1) Берем шар. Среди всех подходящих корзин для этого шара ищем минимальное кол-во лежащих в них шаров.
3.2) Идём по подходящим корзинам и смотрим равно ли кол-во шаров в текущей корзине минимальному кол-ву шаров найденному в 3.1
3.3) как только нашли подходящую корзину кладём в неё шар, обновляем счетчик из п.2 соответствующий найденной корзине.
3.4) назад к пункту 3.1, берём следующий шар

После я делаю несколько проходов начиная с пункта 3, за счет чего и происходит равномерное распределение.

на практике мне понадобилось 3 прохода по алгоритму для того чтобы добиться приемлемого распределения с разницей между корзинами <1% (от общего кол-ва лежащих в корзине шаров).

Может кому-то пригодится эта ветка. Спасибо за подсказки.

@Ygg · 02.04.2019, 18:27

svrn, на счёт моего варианта, там ошибка. После публикации придумал тесты, где он не работает.

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

Код

Вариант 3
Цветные шары           Корзины

  /---\                +-----+
 /     \               |     |
 |  5  |  ---------->  |     |
 \     /      ------>  |     |
  \---/      /         +-----+
            /
  /---\    /           +-----+
 /     \  /            |     |
 | 10  |  ---------->  |     |
 \     /  \            |     |
  \---/    \           +-----+
            \
             \         +-----+
              ------>  |     |
                       |     |
                       |     |
                       +-----+




Вариант 4
Цветные шары           Корзины

  /---\                +-----+
 /     \               |     |
 |  5  |  ---------->  |     |
 \     /  \            |     |
  \---/    \           +-----+
            \
             \         +-----+
              ------>  |     |
                       |     |
              ------>  |     |
             /         +-----+
            /
  /---\    /           +-----+
 /     \  /            |     |
 | 10  |  ---------->  |     |
 \     /  \            |     |
  \---/    \           +-----+
            \
             \         +-----+
              ------>  |     |
                       |     |
                       |     |
                       +-----+

Если пункт 4 пересмотреть, то можно заставить алгоритм работать и на этих тестах. Нужно сравнивать не количество шаров разных цветов, а количество шаров делённое на количество корзин, в которые их можно положить. Получается, наверное, что-то вроде "потока", про который вы говорили ранее. Сейчас попробую с вашим алгоритмом потестю

@svrn · 02.04.2019, 19:25 **[ТС]**

Ygg, стоит оговорится, что это получился алгоритм скорее не равномерного распределения, а алгоритм максимизирующий кол-во шаров в каждой корзине. То есть вполне возможна ситуация в которой у вас 10 корзин с примерно равным количеством, и одна корзине с намного большим количеством, так как эта большая корзина принимает бОльшее количество цветов, чем остальные.

@Ygg · 02.04.2019, 19:34

Не очень понимаю ваш алгоритм. Предположим, что в вашем пункте (3) кладётся один шар выбранного цвета, далее выбирается другой цвет. Пока не пройдём по всем цветам к использованным цветам не возвращаемся. Тогда успешность будет зависеть от порядка, в котором заданы цвета и связи с корзинами.

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

Код

  /---\                +-----+
 /     \               |     |
 |  2  |  ---------->  |  0  |
 \     /  \            |     |
  \---/    \           +-----+
            \
             \         +-----+
              ------>  |     |
                       |  0  |
              ------>  |     |
             /         +-----+
            /
  /---\    /           +-----+
 /     \  /            |     |
 |  1  |  ---------->  |  0  |
 \     /               |     |
  \---/                +-----+



Шаг 1.
       Ошибка                             Успех

  /---\                +-----+       /---\                +-----+
 /     \               |     |      /     \               |     |
 |  1  |  ---------->  |  1  |      |  1  |  ---------->  |  1  |
 \     /  \            |     |      \     /  \            |     |
  \---/    \           +-----+       \---/    \           +-----+
            \                                  \
             \         +-----+                  \         +-----+
              ------>  |     |                   ------>  |     |
                       |  0  |                            |  0  |
              ------>  |     |                   ------>  |     |
             /         +-----+                  /         +-----+
            /                                  /
  /---\    /           +-----+       /---\    /           +-----+
 /     \  /            |     |      /     \  /            |     |
 |  1  |  ---------->  |  0  |      |  1  |  ---------->  |  0  |
 \     /               |     |      \     /               |     |
  \---/                +-----+       \---/                +-----+


Шаг 2.
       Ошибка                             Успех

  /---\                +-----+       /---\                +-----+
 /     \               |     |      /     \               |     |
 |  1  |  ---------->  |  1  |      |  1  |  ---------->  |  1  |
 \     /  \            |     |      \     /  \            |     |
  \---/    \           +-----+       \---/    \           +-----+
            \                                  \
             \         +-----+                  \         +-----+
              ------>  |     |                   ------>  |     |
                       |  1  |                            |  0  |
              ------>  |     |                   ------>  |     |
             /         +-----+                  /         +-----+
            /                                  /
  /---\    /           +-----+       /---\    /           +-----+
 /     \  /            |     |      /     \  /            |     |
 |  0  |  ---------->  |  0  |      |  0  |  ---------->  |  1  |
 \     /               |     |      \     /               |     |
  \---/                +-----+       \---/                +-----+


Шаг 3.
       Ошибка                             Успех

  /---\                +-----+       /---\                +-----+
 /     \               |     |      /     \               |     |
 |  0  |  ---------->  |  2  |      |  0  |  ---------->  |  1  |
 \     /  \            |     |      \     /  \            |     |
  \---/    \           +-----+       \---/    \           +-----+
            \                                  \
             \         +-----+                  \         +-----+
              ------>  |     |                   ------>  |     |
                       |  1  |                            |  1  |
              ------>  |     |                   ------>  |     |
             /         +-----+                  /         +-----+
            /                                  /
  /---\    /           +-----+       /---\    /           +-----+
 /     \  /            |     |      /     \  /            |     |
 |  0  |  ---------->  |  0  |      |  0  |  ---------->  |  1  |
 \     /               |     |      \     /               |     |
  \---/                +-----+       \---/                +-----+

@svrn · 03.04.2019, 10:20 **[ТС]**

Ygg, да, верно, если сделать один проход распределения. Но как я говорил я делаю ТРИ прохода, то есть первый - это начальное распределение, а 2ой и 3ий - это уже перераспределение. То есть на первом проходе я просто раскладываю шары по принципу, где меньше всего туда и кладём, а последующие проходы опять же идет по шарам по матрице смежности, но уже смотрим есть ли корзина с меньшим кол-вом шаров, куда можно переложить текущий шар из той корзины, к которой в которую он был положен на первом проходе.

На 2ом и 3ем проходе шар из второй корзины левой стороны вашего примера будет переложен в третью корзину, после чего на 3ем проходе - шар из первой корзины будет перераспределен во вторую, и мы получим необходимое нам 1-1-1 распределение.

@Ygg 2708 / 862 / 326 Регистрация: 10.02.2018 Сообщений: 2,042
	02.04.2019, 18:27	11
	svrn, на счёт моего варианта, там ошибка. После публикации придумал тесты, где он не работает. Кликните здесь для просмотра всего текста Код Вариант 3 Цветные шары Корзины /---\ +-----+ / \ \| \| \| 5 \| ----------> \| \| \ / ------> \| \| \---/ / +-----+ / /---\ / +-----+ / \ / \| \| \| 10 \| ----------> \| \| \ / \ \| \| \---/ \ +-----+ \ \ +-----+ ------> \| \| \| \| \| \| +-----+ Вариант 4 Цветные шары Корзины /---\ +-----+ / \ \| \| \| 5 \| ----------> \| \| \ / \ \| \| \---/ \ +-----+ \ \ +-----+ ------> \| \| \| \| ------> \| \| / +-----+ / /---\ / +-----+ / \ / \| \| \| 10 \| ----------> \| \| \ / \ \| \| \---/ \ +-----+ \ \ +-----+ ------> \| \| \| \| \| \| +-----+ Если пункт 4 пересмотреть, то можно заставить алгоритм работать и на этих тестах. Нужно сравнивать не количество шаров разных цветов, а количество шаров делённое на количество корзин, в которые их можно положить. Получается, наверное, что-то вроде "потока", про который вы говорили ранее. Сейчас попробую с вашим алгоритмом потестю 0

@svrn 1 / 1 / 0 Регистрация: 22.03.2019 Сообщений: 8
		1
	Задача равномерного распределения 22.03.2019, 10:59. Показов 6042. Ответов 13 Метки нет (Все метки) Здравствуйте, нужна помощь с поиском подходов к решению. Формально задачу можно сформулировать так: Дано множество разноцветных шаров (один шар - один цвет), и несколько корзин, для которых обозначено какие цвета можно в эти корзины класть (одна корзина - от одного цвета и больше). Необходимо разложить шары по корзинам так, чтобы кол-во шаров в корзине было равным насколько это возможно. 1

@vantfiles 1017 / 1904 / 178 Регистрация: 07.05.2013 Сообщений: 3,931 Записей в блоге: 12
	22.03.2019, 14:23	2
	в корзинЕ или в корзинАХ ? 0

@svrn 1 / 1 / 0 Регистрация: 22.03.2019 Сообщений: 8
	25.03.2019, 10:32 [ТС]	3
	В корзинах. Я пришел к следующему алгоритму: представить всё в виде двудольного графа, где первая доля - множество шаров, вторая доля - множество корзин, ребро - гарантия что шар подходит к корзине. первую долю отсортировать по величине степени вершин по возрастанию, т.е. самые редкие и невостребованные цвета будут распределятся первыми; вторую долю отсортировать по степени вершин по убыванию, т.е. корзины с бОльшим количеством принимаемых цветов в верху. После построения графа и сортировки идём по первой доле и распределяем шары, при этом запоминая в какую корзину положили последний шар, и когда начинаем распределять следующий шар, то корзину для него ищем начиная с текущей корзины в памяти. Это даст нам равномерное распределение шаров одного цвета по корзинам, которые этот цвет принимают, но естественно не гарантирует равного кол-ва шаров во всех корзинах. Над этим ещё думаю. 0

@svrn 1 / 1 / 0 Регистрация: 22.03.2019 Сообщений: 8
	25.03.2019, 19:08 [ТС]	4
	Итак, мой алгоритм над которым я думал - фигня. Если на этот раз я не ошибаюсь, то самым логичным методом будет нахождение максимального потока минимальной стоимости в графе на основе описанного мной выше двудольного графа. И по моей логике для нахождения стоимости для ребра нужно использовать функцию, которая возвращает величину прямо пропорциональную количеству уже лежащих в корзине шаров. Пытаюсь пока искать методы и реализации. Но не до конца уверен что в качестве стоимости можно использовать функции. 0

@Дмитррр 43 / 31 / 3 Регистрация: 27.03.2016 Сообщений: 116
	27.03.2019, 21:29	5
	Ты бы задачу сформулировал более чётко. Ответ-то, думаю простой найдётся. Сообщение от svrn Дано множество разноцветных шаров Конечное или бесконечное? Вероятность или количество каждого конкретного цвета известно или нет? Сообщение от svrn какие цвета можно в эти корзины класть В любой пропорции? Сообщение от svrn кол-во шаров в корзине было равным Только по количеству и всё? Если шаров конечное количество, то их надо разместить все? 0

@svrn 1 / 1 / 0 Регистрация: 22.03.2019 Сообщений: 8
	28.03.2019, 22:59 [ТС]	6
	Пытался на скорую руку формализовать задачу. Итак, дано конечное количество разноцветных шаров, цвет каждого шара известен заранее. Дано некоторое количество корзин, принимающих один или несколько цветов. Задача разместить шары в корзинах максимально равномерно по количеству, без пропорций и каких либо доп. критериев. Для условности можно считать что для каждого шара есть корзина принимающая его цвет. По факту это классическая задача о назначениях, в которой работнику можно назначить несколько работ, и нужно равномерно распределить работы среди работников. При этом считаем что время выполнения любой работы константа. 0

@Дмитррр 43 / 31 / 3 Регистрация: 27.03.2016 Сообщений: 116
	29.03.2019, 12:50	7
	Остался вопрос (№1): шары нужно все использовать или не все? Если не все, то сколько нужно. Если любое количество, то положил в каждую корзину по одному шару и задача выполнена. А если нужны все, то равномерность абсолютно не гарантирована. Например, синих шаров 100, а синяя корзина одна; красных шаров 3, а корзин 5. И ещё вопрос (№2): нужно ли использовать каждый цвет шара? Если у меня белая корзина и чёрно-белая, то могу её заполнить только белыми шарами, забив на чёрные? Но в любом случае подход должен быть примерно таким: 1. посчитать количество шаров каждого цвета и корзин каждого цвета; 2. Дальше надо понять какое количество шаров надо в корзины - для одноцветных корзин просто: соотношение количества определённых шаров к количеству таких же одноцветных корзин. Это будет максимум заполнения всех корзин. - для многоцветных вот самое сложное. Нужна пирамидка условий... Например, есть шары шА и шБ. И корзины кА, кБ и кАБ. Если шА меньше чем шБ в 2 и более раз, то всё понятно: Все шА в кА, а шБ в кБ и кАБ. Если разница меньше, чем в 2 раза , то надо считать пропорцию. (шА+шБ)/(кА+кБ+кАБ). Это и будет количество шаров в корзинах. Но если корзин больше, то придётся перебирать много условий. Но тут важно понять, что однозначного распределение шаров может не быть. 3. далее собственно можно начать заполнять корзины до нужного количества. Начать лучше с того цвета, который дал ограничение, т.к. остальных есть с запасом. Последовательность заполнения в общем случае произвольная, если нет никаких дополнительных ограничений (например, на основе моего второго вопроса в этом сообщении). Есть другой вариант. последовательное заполнение. 1. Берём случайный шар и кладём в случайную подходящую корзину. 2. Берём следующий отличный от первого и кладём в отличную от первой корзину. 3. Так перебираем все цвета шаров складируя во все корзины по порядку. 4. Если очередной взятый шар нельзя положить в корзину так, чтобы разница шаров в корзинах не превышала единицу, то берём шар другого цвета. 5. Если попробовав все цвета шаров ни один не подошёл, то для надо берём опять все шары поочереди и не просто пробуем положить в очередную корзину, а ещё рассматриваем перенос/обмен шаров между многоцветными корзинами. 1

@svrn 1 / 1 / 0 Регистрация: 22.03.2019 Сообщений: 8
	29.03.2019, 13:29 [ТС]	8
	ответ на вопрос №1: Шары нужно использовать все по максимуму. ответ на вопрос №2: При распределении нужно учитывать только основное требование равномерного распределения. Касаемо пирамидки условий - это будет дерево решений, где решение положить шар в корзину это отдельная ветка от узла. Мне кажется не самое подходящее решение, уж слишком накладно для вычисления. Ориентировочно можно думать о 100 000 шаров и 1000 корзин, и 256 цветах. Второй вариант это по сути и есть алгоритм поиска максимального потока минимальной стоимости, просто описан довольно формально. Там мы тоже сначала раскидываем шары по максимуму, а потом пытаемся перекладывать, что бы "удешевить" нахождение шара в корзине. Соответственно если стоимость укладки шара в корзину равна скажем кол-ву шаров в корзине +1, то по идее алгоритм должен максимально равномерно разложить шары в многоцветных корзинах и при этом максимально заполнить "предельные" корзины (100 зеленых шаров и только 1 зеленая корзина). Я нашел похожую задачу в семинаре для первого курса какого то ВУЗа, и поэтому мне подумалось, что задача довольно распространенная и простая. Хотя гугление не дало мне практически никаких результатов. 0

@Ygg 2708 / 862 / 326 Регистрация: 10.02.2018 Сообщений: 2,042
	29.03.2019, 16:39	9
	Сообщение было отмечено svrn как решение Решение Исписал пару листочков и родил такой алгоритм: На каждом шаге алгоритма выбираем корзину, выбираем для неё шар, кладём выбранный шар в выбранную корзину. Повторяем пока не закончатся все шары. 1) Исключаем корзины, в которые ничего нельзя положить. 2) Из оставшихся выбираем корзину, в которой меньше всего шаров. 3) Если таких корзин несколько, то выбираем такую, для которой количество возможных шаров минимально. Пояснение к пункту 3 Пусть у нас есть N красных и M чёрных шаров. И все эти цвета могут быть положены в корзину. Тогда максимальное количество шаров в корзине будет равно (N+M). Для каждой корзины можно найти свой максимум. Нам нужна корзина, максимум которой самый маленький из всех. При этом, на каждом шаге алгоритма один из шаров будет оказываться в какой-то корзине. Поэтому максимумы будут постоянно меняться. Кроме того, если в корзине уже лежит какое-то количество шаров, то их нужно приплюсовать к максимуму возможных. 4) Для выбранной корзины смотрим, какие цвета в неё можно положить. Если цветов несколько, то выбираем цвет по наибольшему количеству оставшихся шаров данного цвета. На двух примерах вроде работает. На большее количество тестов меня не хватило. Кликните здесь для просмотра всего текста Код Вариант 1 Цветные шары Корзины /---\ +-----+ / \ \| \| \| 4 \| ----------> \| \| \ / ------> \| \| \---/ / +-----+ / /---\ / +-----+ / \ / \| \| \| 6 \| ----------> \| \| \ / \| \| \---/ +-----+ Вариант 2 Цветные шары Корзины /---\ +-----+ / \ \| \| \| 5 \| ----------> \| \| \ / \ \| \| \---/ \ +-----+ \ \ +-----+ ------> \| \| \| \| ------> \| \| / +-----+ / /---\ / +-----+ / \ / \| \| \| 6 \| ----------> \| \| \ / \| \| \---/ +-----+ 1

@svrn 1 / 1 / 0 Регистрация: 22.03.2019 Сообщений: 8
	02.04.2019, 17:27 [ТС]	10
	Ygg, скорее всего это самый приемлемый алгоритм. Мне правда он показался довольно перегруженным поиском минимумом/максимов. Я решил делать следующим образом: 1) сначала формируем матрицу смежности шаров/корзин. Будем считать что для каждого шара есть корзина, и наоборот. 2) в отдельном массиве считаем сколько шаров в какой корзине лежит. То есть просто счетчик количества шаров в корзине. 3) бежим по матрице смежности по шарам. 3.1) Берем шар. Среди всех подходящих корзин для этого шара ищем минимальное кол-во лежащих в них шаров. 3.2) Идём по подходящим корзинам и смотрим равно ли кол-во шаров в текущей корзине минимальному кол-ву шаров найденному в 3.1 3.3) как только нашли подходящую корзину кладём в неё шар, обновляем счетчик из п.2 соответствующий найденной корзине. 3.4) назад к пункту 3.1, берём следующий шар После я делаю несколько проходов начиная с пункта 3, за счет чего и происходит равномерное распределение. на практике мне понадобилось 3 прохода по алгоритму для того чтобы добиться приемлемого распределения с разницей между корзинами <1% (от общего кол-ва лежащих в корзине шаров). Может кому-то пригодится эта ветка. Спасибо за подсказки. 0

	03.04.2019, 10:20

@svrn 1 / 1 / 0 Регистрация: 22.03.2019 Сообщений: 8
	02.04.2019, 19:25 [ТС]	12
	Ygg, стоит оговорится, что это получился алгоритм скорее не равномерного распределения, а алгоритм максимизирующий кол-во шаров в каждой корзине. То есть вполне возможна ситуация в которой у вас 10 корзин с примерно равным количеством, и одна корзине с намного большим количеством, так как эта большая корзина принимает бОльшее количество цветов, чем остальные. 0

@svrn 1 / 1 / 0 Регистрация: 22.03.2019 Сообщений: 8
	03.04.2019, 10:20 [ТС]	14
	Ygg, да, верно, если сделать один проход распределения. Но как я говорил я делаю ТРИ прохода, то есть первый - это начальное распределение, а 2ой и 3ий - это уже перераспределение. То есть на первом проходе я просто раскладываю шары по принципу, где меньше всего туда и кладём, а последующие проходы опять же идет по шарам по матрице смежности, но уже смотрим есть ли корзина с меньшим кол-вом шаров, куда можно переложить текущий шар из той корзины, к которой в которую он был положен на первом проходе. На 2ом и 3ем проходе шар из второй корзины левой стороны вашего примера будет переложен в третью корзину, после чего на 3ем проходе - шар из первой корзины будет перераспределен во вторую, и мы получим необходимое нам 1-1-1 распределение. 0

Задача равномерного распределения

Решение