将自然数表示为不同平方的总和 [英] Represent natural number as sum of distinct squares

问题描述

问题是找到正整数的最大集合S，以使S的元素的平方和等于给定数字n。

The problem is to find the largest set S of positive integers such that the sum of the squares of the elements of S is equal to a given number n.

例如：

4 =2²

20 =4²+2²

38 =5² +3²+2²

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

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

我有一种算法，运行时间为 O（2 ^（sqrt n）* n），但是它太慢了（每个正方形的子集）。

I have an algorithm that runs in time O(2^(sqrt n) * n), but it's too slow (every subset of squares).

推荐答案

有一个基于规范动态的 O（n ^ 1.5）时间算法子集总和的程序。这是递归：

There's an O(n^1.5)-time algorithm based on the canonical dynamic program for subset sum. Here's the recurrence:

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)

为中的所有 m 计算 C（m，k） 0..n 和 0..floor（n ^ 0.5）中的所有 k 。返回 C（n，floor（n ^ 0.5））作为目标值。要恢复该集合，请追溯argmaxes。

Compute C(m, k) for all m in 0..n and all k in 0..floor(n^0.5). Return C(n, floor(n^0.5)) for the objective value. To recover the set, trace back the argmaxes.

这篇关于将自然数表示为不同平方的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！