用于计算形成100的组合数的算法

Question

我遇到了一个棘手的情况,我需要根据不同的因素来计算形成100的组合数.

那些是

• 组合数量
• 乘法因子
• 距离

样本输入1:(2-10-20)

它的意思是

• 列出有效的2路组合,形成100.
• 组合之间的距离应小于或等于20.
• 并且所有得到的组合必须能够被给定的乘法因子10整除

输出将是

[40,60]

[50,50]

[60,40]

这里[30,70],[20,60]无效,因为距离超过20.

样本输入2:[2-5-20]

[40,60]

[45,55]

[50,50]

[55,45]

[60,40]

如果你引导我走向正确的方向,我将非常感激.

干杯.

Answer 1

我希望这不是一个家庭作业问题!

    def combinations(n: Int, step: Int, distance: Int, sum: Int = 100): List[List[Int]] =
      if (n == 1) 
        List(List(sum))
      else 
        for {
          first <- (step until sum by step).toList
          rest <- combinations(n - 1, step, distance, sum - first)
          if rest forall (x => (first - x).abs <= distance)
        } yield first :: rest

Answer 2

如果需要将最大距离N除以100,则组合中的最小值为

100/2 - N/2

如果你需要将最多距离为N的3个值除以100,这就变得更加棘手.3个值的平均值为100/3,但如果其中一个值远低于此平均值,则其他值只能略大于此平均值,这意味着最小值不是平均值减去最大距离两个,但可能

100/3 - 2N/3

通常,对于M值,这变为

100/M - (M-1)N/M.

哪个可以简化为

(100 - (M-1)N)/ M.

同样,我们可以计算出最高可能值:

(100 +(M-1)N)/ M.

这为您提供了组合的第一个值的范围.

要确定第二个值的范围,您必须考虑以下约束:

• 与第一个值的距离(不应高于您的最大距离)
• 我们还能达到总和(100)

第一个约束不是问题.第二是.

假设我们将100除以3除以最大距离30,使用10的倍数.如前所计算,最小值为:

(100 - (3-1)30)/ 3 - > 13 - >四舍五入到下一个10 - > 20的倍数

最大值是

(100 +(3-1)30)/ 3 - > 53 - >四舍五入到前一个10 - > 50的倍数

所以对于第一个值,我们应该迭代20,30,40和50.

假设我们选择20.这为其他2个值留下80.我们再次分配80超过2个值,最大距离为30,这给出:

最小值:(80 - (2-1)30)/ 2 - > 25 - >舍入 - > 30

最大值:(80 +(2-1)30)/ 2 - > 55 - >舍入 - > 50

第二个限制是我们不希望与第一个值相比大于30的距离.这至少为-10,最大为50.

现在取两个域之间的交集 - > 30到50,第二个值迭代超过30,40,50.

然后重复此操作以获取下一个值.

编辑: 我在伪代码中添加了算法,使其更清晰:

calculateRange (vector, remainingsum, nofremainingvalues, multiple, maxdistance)
{
if (remaingsum==0)
   {
   // at this moment the nofremainingvalues should be zero as well
   // found a solution
   print vector
   return;
   }

minvalueaccordingdistribution = (remainingsum-(nofremainingvalues-1)*maxdistance)/nofremaingvalues;
maxvalueaccordingdistribution = (remainingsum+(nofremainingvalues-1)*maxdistance)/nofremaingvalues;

minvalueaccordingdistance = max(values in vector) - maxdistance;
maxvalueaccordingdistance = min(values in vector) + maxdistance;

minvalue = min (minvalueaccordingdistribution, minvalueaccordingdistance);
maxvalue = max (minvalueaccordingdistribution, minvalueaccordingdistance);

for (value=minvalue;value<=maxvalue;value+=multiple)
   {
   calculaterange (vector + value, remainingsum - value, nofremainingvalues-1, multiple, maxdistance);
   }
}

main()
{
calculaterange (emptyvector, 100, 2, 20);
}