问题是找到最大的正整数集合S,使得S的元素的平方和等于给定数n。
例如:
4 = 2²
20 = 4² + 2²
38 = 5² + 3² + 2²
300 = 11² + 8² + 7² + 6² + 4² + 3² + 2² + 1².
我有一个运行时间 O(2^(sqrt n) * n)
的算法,但它太慢了(正方形的每个子集)。
最佳答案
有一个 O(n^1.5)
时间算法基于 subset sum 的规范动态程序.这是重复的:
C(m, k) is the size of the largest subset of 1..k whose squares sum to m
C(m, k), m < 0 = -infinity (infeasible)
C(0, k) = 0
C(m, 0), m > 0 = -infinity (infeasible)
C(m, k), m > 0, k > 0 = max(C(m, k-1), C(m - k^2, k-1) + 1)
为 0..n
中的所有 m
和所有 k
计算 C(m, k)
0..floor(n^0.5)
。为目标值返回 C(n, floor(n^0.5))
。要恢复集合,请追溯 argmax。
关于algorithm - 将自然数表示为不同平方和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26222693/