Представьте натуральное число как сумму различных квадратов

Задача состоит в том, чтобы найти наибольшее множество 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), но он слишком медленный (каждое подмножество квадратов).


algorithm number-theory
person Eryk Pawilan    schedule 06.10.2014    source источник
comment
Итак, проблема в том, что вам нужен более быстрый алгоритм?   -  person Werner    schedule 06.10.2014
comment
К сожалению, мое решение слишком медленное.   -  person Eryk Pawilan    schedule 06.10.2014
comment
Это просто не было ясно из вашего вопроса, поскольку вы вообще не упоминаете об этом.   -  person Werner    schedule 06.10.2014
comment
Пример, который вы привели, неверен. 300 можно записать как 11² + 8² + 7² + 6² + 4² + 3² + 2² + 1².   -  person Juan Lopes    schedule 06.10.2014
comment
ОП, ты знаком с динамическим программированием? Вы можете прочитать об этом в любой хорошей книге по алгоритмам.   -  person Colonel Panic    schedule 07.10.2014
comment
Кстати, не все числа можно записать в виде суммы различных квадратов. Например 6 или 2.   -  person Colonel Panic    schedule 09.10.2014
comment
Если кому интересно, сильно связанная тема на mathSE. Я не могу доказать, что задачи равны, поэтому я не ставил это (используя это решение наблюдения) в качестве ответа. Возможно, я сделаю это в будущем. Если мои предположения верны, то можно решить за O(N*lg(n)), где N — количество квадратов в сумме.   -  person Tacet    schedule 14.12.2014

Ответы (3)


arrow_upward
7
arrow_downward

Существует O(n^1.5)-временной алгоритм, основанный на канонической динамической программе для суммы подмножества. Вот повторение:

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.

person David Eisenstat    schedule 06.10.2014

arrow_upward
4
arrow_downward

Мне просто интересно, сводится ли эта проблема к NP? Похоже, у вас есть список целых чисел (квадратов) меньше n (может быть сгенерирован в O(sqrt(n))), и вы ищете сумму подмножества размера из 1 to sqrt(n) (проверьте все возможности). Если это так, это должно быть решаемо с помощью алгоритма динамического программирования рюкзака (но это довольно наивный алгоритм, и я думаю, что его можно улучшить) в O(n^2) - sqrt (n) задач, чтобы проверить время sqrt (n) количество предметов в рюкзаке, умноженное на n вес рюкзака.

РЕДАКТИРОВАТЬ: я думаю, что с умным возвратом после заполнения массива динамического программирования вы могли бы сделать это в O(n*sqrt(n)).

person fex    schedule 06.10.2014

arrow_upward
4
arrow_downward

Вы можете использовать повторение:

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]
person Juan Lopes    schedule 06.10.2014