如何在 k 个人之间分配 n 个对象的 x 个副本

Question

>我有以下用例;

我有 N 个不同的项目，每个项目可以有 x 个副本。现在我需要将这些项目分配给 k 个人，其中每个人的能力各不相同，可以 <=N。

必须满足以下条件;

每个人都应该获得一份且只能获得一份物品副本

例：

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的任意数字分配它时，我有时会遇到这样一种情况：我留下了一些项目要分配，因为我无法确保"每个人都应该获得一个且只有一个项目副本"的条件

Answer 1

由于每个项目都有相同的"权重"，因此您实际上可以贪婪地解决这个问题。为了确保每个人收到不同的物品，我们通过重复N不同物品的序列x次来创建包含所有xN物品的序列。然后，我们仔细检查每个人，简单地删除并分配给他们这个序列的前c个项目，其中c是那个人的承载能力。

这是有效的，因为我们布置项目的方式和因为c <= N.在我们的"巨型"序列中，重复项总是彼此相距N索引，因此c连续元素永远不会包含两个重复项。重复项将仅出现在包含N个以上项目的连续子序列中。

请注意，在此算法的实现中，您实际上不必创建兆序列;您可以使用模块化算术简单地重复遍历不同的项序列。为了保持解释简单，我将在示例中形成"mega"项序列，但您不必在实现中执行此操作。

以您问题中的示例为例，让 3 个不同的项目A, B, C，每个项目有 3 个副本。"巨型"序列是通过重复不同的项目序列 3 次而形成的：A, B, C, A, B, C, A, B, C.现在我们检查每个人，并简单地为他们分配他们可以携带的物品数量。为了说明这一点，请考虑容量阵列的以下情况(取自下面的问题和评论(：

• [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。