如何根据文件大小将文件平均分配给用户

Question

我有N个不同文件大小的文件，还有M个用户。

我想做的是使用C#、C++或伪代码中的算法，将文件平均分配给用户。

如果游戏中没有文件大小，那么每个用户的文件数大约为N/M。因此，我可以为每个用户随机选择N/M个文件（如果M>N并且没有留下更多文件，可能有些用户无法参加）。但是，现在我在游戏中有了文件大小，我想在考虑到文件大小的情况下自动将文件分配给用户。

一个文件只能与一个用户相关。因此，当一个文件与用户相关时，它就不能再使用了。

一个用户可以与许多文件相关。

如果文件少于用户（N>M），则一些用户可能会或许多用户根本不参加。

此外，这些情况可能是N<M、 M>N和M=N，并且该算法应当将文件平均地分配给用户。

如果有人能帮我，我将不胜感激。

谢谢。

Answer 1

如果这是家庭作业，那就太糟糕了！

这是分区问题的优化版本，它是NP难的（即，即使只有两个用户，你也无法有效地解决它）。

有一种贪婪算法，它给出了最佳排列的适当近似，并在O(n log n)时间内完成。如果我是你的话，我会这么做，除非你非常清楚地需要完美的最优性。这是一个伪代码，取自我上面链接的维基百科页面。它适用于两个集合（即M=2），但很容易推广。基本思想是，在每个阶段，将当前文件分配给总数最小的用户。

INPUT:  A list of integers S
OUTPUT: An attempt at a partition of S into two sets of equal sum
1 function find_partition(S):
2     A ← {}
3     B ← {}
4     sort S in descending order
5     for i in S:
6         if sum(A) <= sum(B)
7             add element i to set A
8         else
9             add element i to set B
10    return {A, B}

完美最优性原则上是可以实现的，但有两个问题需要考虑。

1. 如果没有其他功能，您可以尝试将文件分配给用户的所有可能的操作。这将是非常低效的，但众所周知，这是一个NP难题，这意味着无论你做什么，你都会得到一个指数运行时间的问题
2. 在两个以上用户的情况下，最优意味着什么还不完全清楚。（对于两个用户来说很清楚，这就是为什么分区问题用两个来表示的原因。）例如，假设您有八个用户。[8,4,4,4,4,4,4,0]和[5,5,5,5,3,3,3,3]哪个分配更好？您需要一些定义明确的指标来确定分配的"糟糕程度"，然后才能尝试将其最小化