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))

如果桶的数量是动态的，你就得聪明一点，但这种方法基本上是可行的。