找到十个大于 0 且总和为 2011 但它们的倒数总和为 1 的算法

Question

找出十个整数>0，总和为 2011 但它们的倒数总和为 1

例如

x1+x2+..+x10 = 2011

1/x1+1/x2+..+1/x10 = 1

我在这里发现了这个问题http://blog.computationalcomplexity.org/2011/12/is-this-problem-too-hard-for-hs-math.html

我想知道计算复杂度是多少，什么类型的算法可以解决它。

编辑2:我写了以下足够快的暴力破解代码。我没有找到任何解决方案，所以我需要稍微调整一下我的假设。我现在有信心找到解决方案。

 from fractions import Fraction

pairs = [(i,j) for i in range(2,30) for j in range(2,30)]

x1x2 = set((i+j, Fraction(1,i)+Fraction(1,j)) for i,j in pairs)

print('x1x2',len(x1x2))

x1x2x3x4 = set((s1+s2,f1+f2) for s1,f1 in x1x2 for s2,f2 in x1x2 if f1+f2<1)

print('x1x2x3x4',len(x1x2x3x4))

count = 0
for s,f in x1x2x3x4:
    count+=1
    if count%1000==0:
        print('count',count)
    s2 = 2011 - s
    f2 = 1 - f
    for s3,f3 in x1x2:
        s4 = s2-s3
        if s4>0:
            f4 = f2-f3
            if f4>0:
                if (s4,f4) in x1x2x3x4:
                    print('s3f3',s3,f3)
                    print('sf',s,f)

Answer 1

请注意，您不能为单个问题实例定义计算复杂度，因为一旦您知道答案，计算复杂度就是 O(1)，即恒定时间。计算复杂性只能定义为无限系列的问题。

解决此类问题的一种方法是使用回溯搜索。您的算法花费太多时间来搜索 10 维空间中不能包含解决方案的部分。一个有效的回溯算法将

• 按照 x₁, x₂, ..., x₁₀ 的顺序给变量赋值
• 保持约束 x₁ <= x₂ <= ... <= x₁₀
• 在搜索过程中，总是在分配了数字 xi 时
  • 令 S = x₁ + ... + x_i
  • 令 R = 1/x 1 + ... + 1/x i
  • 始终检查 S <= 2011 - (10 - i) * x_i
  • 始终检查 R <= 1 - (1/[(2011 - S)/(10 - i)])
  • 如果在搜索过程中没有满足这两个约束条件，则无法再找到解决方案，算法应立即回溯。请注意，约束是基于数字按递增顺序分配的事实，即 x_i <= x_i+1 在所有情况下

注意:您可以通过假设所有 x₁, ..., x₁₀ 除给定均匀编号，例如960，也就是你只考虑960除以x_i是整数的x_i。这使得小数部分的计算变得更加容易，而不是检查 1/x 1 + ... 等于 1 你可以检查 960/x 1 + ...等于 960。因为所有除法都是偶数并且返回整数，所以您根本不需要使用 float 或有理数运算，但一切都只适用于整数。当然，固定模数越小，能找到的解就越少，但这也使得搜索速度更快。