Biểu thị số tự nhiên là tổng của các ô riêng biệt

Question

Vấn đề là tìm số S lớn nhất của các số nguyên dương sao cho tổng các bình phương của các phần tử của S bằng với một số n nhất định.

Ví dụ:

4 = 2²
20 = 4² + 2²
38 = 5² + 3² + 2²
300 = 11² + 8² + 7² + 6² + 4² + 3² + 2² + 1².

Tôi có thuật toán chạy theo thời gian O(2^(sqrt n) * n), nhưng quá chậm (mỗi tập hợp con của hình vuông).

Answer 1

Có một thuật toán O(n^1.5) thời gian dựa trên chương trình động chuẩn cho subset sum. Dưới đây là sự tái diễn:

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) 

Tính C(m, k) cho tất cả m trong 0..n và tất cả k trong 0..floor(n^0.5). Trả lại C(n, floor(n^0.5)) cho giá trị mục tiêu. Để khôi phục tập hợp, theo dõi lại argmaxes.

Answer 2

Tôi đã tự hỏi liệu vấn đề này có giảm xuống NP không? Có vẻ như bạn có danh sách các số nguyên (hình vuông) nhỏ hơn n (có thể được tạo trong O(sqrt(n))) và bạn đang tìm tổng kích thước con từ 1 to sqrt(n) (kiểm tra tất cả các vị trí). Nếu vậy nó nên được giải quyết với thuật toán lập trình ba lô năng động (nhưng đây là thuật toán khá ngây thơ và tôi nghĩ rằng nó có thể được cải thiện) trong O(n^2) - sqrt (n) của các vấn đề để kiểm tra lần sqrt (n) knapsack mục đếm lần n knapsack trọng lượng.

EDIT: Tôi nghĩ với tính năng quay lại thông minh sau khi điền mảng lập trình động bạn có thể thực hiện trong O(n*sqrt(n)).

Answer 3

Bạn có thể sử dụng tái phát:

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)) 

Hoặc, trong mã 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) 

Ví dụ bạn đã cung cấp (300), có thể được viết với 8 yếu tố như:

300 = 11² + 8² + 7² + 6² + 4² + 3² + 2² + 1²

Kết quả khác:

4 = sum [4] 
20 = sum [16, 4] 
38 = sum [25, 9, 4] 
300 = sum [121, 64, 49, 36, 16, 9, 4, 1]