algorithm - 创建多个组合，总和为 100

Question

我希望能够在给定定义数量的“桶”和定义的“差异因子”的情况下创建总和为 100% 的多个组合。在下面的示例中，为了简单起见，差异是 20 倍，但我可能会在最终解决方案中将其减少到 1。

例如，使用 3 个“桶”A、B、C，您可以拥有:

A     100     80      80      60      60  ...   0
B     0       20      0       20      40  ...   0
C     0       0       20      20      0   ...   100

每一列都是一个组合(总和为 100)，我想存储它并对其进行进一步计算。

这是一个业务问题，而不是家庭作业。

请帮我想出一个解决方案。一种强力方法是为每种可能的组合创建一个多维数组，例如100x100x100，然后遍历每 100 万个组合，看看哪些组合的总和为 100。然而，这看起来效率太低了。

非常感谢。我希望我已经解释得足够清楚了。

Answer 1

此问题称为 partitions而不是组合，这是不同的。

首先:“差异因子”只是将问题从查找 100 的分区转变为(在您的示例中)查找 5 的分区(然后乘以 20)。

下一步:如果桶的数量是恒定的，你可以这样做(伪代码):

for i = 0 to n
  for j = 0 to n-i
    output (i, j, n-(i+j))

如果桶的数量是动态的，你就必须更聪明一点，但这种方法基本上是有效的。