Как распределить x копию n объектов среди k человек - PullRequest
Новая
       73

Как распределить x копию n объектов среди k человек

0 голосов
/ 19 июня 2020

У меня следующий вариант использования:

У меня есть N различных элементов, каждый может иметь x количество копий. Теперь мне нужно распределить эти предметы среди k человек, где возможности каждого человека различаются и могут быть <= N. </p>

Должны быть выполнены следующие условия:

Каждый человек должен получить одну и только одну копию Товара

Пример: 

Items = apple , banana , orange
copies = 3 ( It means we have 3 apples , 3 bananas and 3 oranges )
So I have a array;
{1,2,3,4,5,6,7,8,9} // 1,2,3 = 3 apples ; 4,5,6 = 3 banana ; 7,8,9 = 3 oranges
Total Person = 5
Person     Capacity
P1         3
P2         2
P3         1
P4         1
P5         2

Как решить такую ​​проблему? Проблема, с которой я сталкиваюсь, заключается в том, что, когда я выделяю его для произвольных чисел для N, x, k, я иногда попадаю в ситуацию, когда мне остается выделить некоторые элементы, потому что я не могу гарантировать условие, что «Каждый человек должен получить одну и только одну копию Предмета "

1 Ответ

0 голосов
/ 19 июня 2020

Так как каждый предмет имеет одинаковый «вес», вы можете решить эту проблему жадно. Чтобы гарантировать, что каждый человек получит отдельные элементы, мы создаем последовательность, содержащую все xN элементы, повторяя последовательность N отдельных элементов x раз. Затем мы go через каждого из людей и просто удаляем и назначаем им первые c элементы этой последовательности, где c - это пропускная способность этого человека.

Это работает из-за того, как мы выложили пункты и т.к c <= N. В нашей "мегапоследовательности" дубликаты всегда находятся на расстоянии N индексов друг от друга, поэтому c последовательных элементов никогда не будут содержать двух дубликатов. Дубликаты будут появляться только в смежных подпоследовательностях, содержащих более N элементов.

Обратите внимание, что при реализации этого алгоритма вам фактически не нужно создавать мегапоследовательность; вы можете просто многократно перебирать отдельные последовательности элементов, используя модульную арифметику c. Чтобы не усложнять объяснение, я буду формировать последовательность «мега» элементов в примерах, но вам не обязательно делать это в реализации.

В примере из вашего вопроса позвольте 3 различным items be A, B, C по 3 копии каждая. «Мега» последовательность формируется путем повторения последовательности отдельных элементов 3 раза: A, B, C, A, B, C, A, B, C. Теперь мы go через каждого человека и просто назначаем им количество предметов, которые они могут нести. Чтобы проиллюстрировать это, рассмотрим следующие случаи для массива емкости (взятые из вашего вопроса и комментариев ниже):

  • [3, 2, 1, 1, 2]: P1 получает A, B, C, P2 получает A, B, P3 получает C, P4 получает A, а P5 получает B, C.
  • [2, 2, 2, 2, 1]: P1 получает A, B, P2 получает C, A, P3 получает B, C, P4 получает A, B, и P5 получает C.
  • [3, 1, 1, 1, 1, 2]: P1 получает A, B, C, P2 получает A, P3 получает B, P4 получает C, P5 получает A, P6 получает B, C.
...