算法:挑选 n 个不同重量的元素以获得平均元素重量

Question

我有 5 个文件夹，每个文件夹包含大小为 10KB、500KB、1MB、5MB 和 30MB 的“n”个文件。现在我需要从这些文件夹中选择正好 15000 个文件并将它们放入一个新文件夹中，这样我就可以从每个文件夹中选择至少一个文件和 平均文件大小保持在 1MB 左右。我已经尝试处理加权平均分布以及这个问题 http://goo.gl/uAHOk1但无法得出任何结论。

这个问题可以在多项式时间内解决吗？

编辑

来自评论:

1. 为了清楚起见，您可以认为每个文件夹正好有 16k 个文件。
2. 我所说的大约 1 MB 是指平均文件大小在 1 到 1.5 MB 之间。例如，考虑到我的问题的局限性，如果我必须恰好选择 5 个文件，那么唯一的解决方案是从每个文件夹中选择一个文件。然后，平均文件大小将变为 7.3MB

Answer 1

如果您希望平均大小尽可能接近您的值，此问题类似于以下 ILP:

s_ij = size of file i in folder j  [Parameter]
X_ij = select file i from folder j [Binary variable]

max  Sum_ij s_ij * X_ij
such that
Sum_ij s_ij * X_ij <= 15,000 * average_size
Sum_ij X_ij = 15000
Sum_i X_ij >= 1  forall j

这几乎是一个带有额外维度和约束(每个文件夹一个文件)的装箱问题。正如 Harold 提到的，我们可以从遍历每个文件夹并选择一个文件开始——例如最小的一个。这可以在多项式时间内完成。剩下的是装箱问题，您可以从任何文件夹中的任何文件中进行选择，以填补 15,000*average_size 与预选文件总和之间的差距。众所周知，装箱是NP-hard，因此您无法在多项式时间内解决此问题。