algorithm - 如何将 100 个不同的文件放在 20 个文件系统上？

Question

我有 20 个文件系统:

 /fs01
 /fs02
 /fs03
 ...
 /fs20

在我的 Unix 环境中。这些文件系统中的每一个都包含一些可用空间，我可以用它来保存文件。这些文件系统彼此独立，并且各自包含不同数量的可用空间。

我在另一台主机上有 100 个不同大小的文件，我想将这些文件中的每一个都放在任何可用的位置。显然，将文件放置到特定文件系统后，该特定文件系统上的可用空间量将减少文件大小。

我正在寻找一种有效的方法；即一种算法，它获取上述数据作为输入并给我一个像这样的映射:

 /fs01    <- f1,f10,f29
 /fs02    <- f5,f30
 /fs03    <-nothing here. too small.
 ...
 /fs20    <- f89,f100

其中f1是文件1，f2是文件2，等等。 你觉得有没有这样的算法？

Answer 1

在我看来，您可以使用整数规划技术来解决它。

https://en.wikipedia.org/wiki/Integer_programming

那里有很多免费的求解器。

模型很简单。您有 20x100 个变量，可以是 0 或 1。每个变量 x_{i,j} 表示(0:文件不在此文件系统中，1:文件在此文件系统中)。 约束是:

• 每个变量都在 0 和 1 之间(它们是整数，它们是 0 或 1)
• 与一个文件相关的所有变量之和为1(每个文件仅在1个文件系统中)
• 与文件系统相关的所有变量按其大小加权的总和必须小于可用空间。

解决方案空间中的每个点都适合您。