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

Question

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

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

如果文件大小不在游戏中，它会类似于每个用户 N/M 个文件。因此，我可以为每个用户随机选择 N/M 个文件(如果 M > N 并且没有更多文件留下，可能有些用户无法参与)。但是，现在我有了游戏中的文件大小，我想自动将文件分配给考虑到文件大小的用户。

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

一个用户可以关联多个文件。

如果文件少于用户数 (N > M)，一些用户可能或许多根本不参与。

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

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

谢谢。

Answer 1

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

这是partition problem的优化版本，并且它是 NP 难的(即，您将无法有效地解决它)，即使您只有两个用户也是如此。

有一种贪心算法可以对最优排列进行适当的近似，并在 O(n log n) 时间内完成。如果我是你，这就是我会选择的，除非你非常明确地需要完美的最优性。这是伪代码，取 self 上面链接的维基百科页面。它适用于两个集合(即 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 ]？您需要一些明确定义的指标来确定分配的“坏处”，然后才能尝试将其最小化。