Распределение предметов из «х» наборов растений в «у» корзинах поровну

Question

Мне нужны идеи об алгоритме распределения растений по группам. У меня есть, скажем, 5 наборов растений, и каждый набор отображает определенное свойство, например,

setA= {set of all plants that are green in color} 

setB = {set of all plants red in color} 

setC={ all the plants that are roots also} 

setD= {fruits} 

setE= [flowers}

Растение может входить в несколько комплектов. Общее количество растений не равно "n", а у меня есть "m" корзин. Необходимо распределить все эти «n» растений в «m» корзинах так, чтобы для каждого набора во всех корзинах было одинаковое (или почти равное) количество растений из этого набора. И тут возникает проблема. Если я начну распространение в «m» корзинах по одной для каждого набора, то в большинстве сценариев последнее распределение будет единственным допустимым, то есть корзины будут иметь равномерное распределение цветов в них, но не обязательно фруктов , корни или цвета и т. д.

Как распределить ВСЕ эти одинаково? Есть идеи?

Answer 1

Это вариация проблемы максимального соответствия в двудольном графе .

Например, у вас есть 20 растений и 5 групп. Затем первый набор узлов будет состоять из 20 растений, а другой - из 5 корзин, но каждая корзина будет представлена ​​4 раза (всего 20 узлов).
Теперь вам просто нужно сопоставить 20 растений с 20 узлами корзины, что и является проблемой выше.

Если n не делится на m, вы можете добавить несколько запасных узлов busket. Например, если n = 23 и m = 5, вы можете повторить каждую корзину 5 раз. Когда будет найдено идеальное совпадение, у busket-set будут еще два (5*5 - 23) свободных узла.

Чтобы требование «почти равных» работало лучше (когда нет идеального соответствия), вместо этого вы можете сделать график взвешенным. То есть greenPlantsBasket # 1 стоит 1, greenPlantsBasket # 2 стоит 2, greenPlantsBasket # 3 стоит 4 и т. Д.

Википедия предоставляет алгоритмы для всех разновидностей проблемы максимального соответствия, а также есть библиотеки реализации.