Задача состоит в том, чтобы найти наибольшее множество 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) -time, основанный на канонической динамической программе для суммы подмножества. Здесь повторяемость:
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)
Вычислить C(m, k) для всех m в 0..n и всех k в 0..floor(n^0.5). Верните C(n, floor(n^0.5)) для объектного значения. Чтобы восстановить набор, отсканируйте аргументы argmaxes.
Мне просто интересно, уменьшилась ли эта проблема до NP? Похоже, у вас есть список целых чисел (квадратов) меньше n (может быть сгенерирован в O(sqrt(n))), и вы ищете сумму подмножества размером от 1 to sqrt(n) (проверьте все возможности). Если это так, то это должно быть разрешено с помощью алгоритма динамического программирования ранца (но это довольно наивный алгоритм, и я думаю, что его можно было бы улучшить) в O(n^2) - sqrt (n) проблем, чтобы проверять время sqrt (n) числа ранца count count n knapsack вес.
EDIT:
Я думаю, что с помощью интеллектуального backtracking после заполнения массива динамического программирования вы можете сделать это в O(n*sqrt(n)).
Вы можете использовать повторение:
T(0, m) = 0
T(n, m) = -Infinity (if n<0 or m<0)
T(n, m) = max(T(n-m*m, m-1)+1, T(n, m-1))
Или, в коде Python:
from functools import lru_cache
@lru_cache(100000)
def T(n, m):
if n<0 or m<0: return (-1000000, 0)
if n==0: return (0, 0)
return max((T(n-m*m, m-1)[0]+1, m), T(n, m-1))
def squares(n):
s = int(n**0.5)
while n>0 and s>0:
_, factor = T(n, s)
yield factor**2
n -= factor**2
s = factor-1
for x in (4, 20, 38, 300):
result = list(squares(x))
print(sum(result), '= sum', result)
Пример, который вы дали (300), можно записать с 8 факторами:
300 = 11² + 8² + 7² + 6² + 4² + 3² + 2² + 1²
Другие результаты:
4 = sum [4]
20 = sum [16, 4]
38 = sum [25, 9, 4]
300 = sum [121, 64, 49, 36, 16, 9, 4, 1]