我有以下代码执行得太慢。这个想法类似于0/1背包问题，您有一个给定的整数n，并且必须找到范围为1到n-1的数字，这些数字在平方时加起来等于n平方。
例如，如果n为5，则应输出3，4，因为3 ** 2和4 ** 2 =（25或5 ** 2）。我一直在努力了解如何提高效率，并想了解用于提高此类程序效率的概念。
[其他一些示例：n = 8 [无] n = 30 [1、3、7、29] n = 16 [2、3、5、7、13]
我发现了一些与此相关的帖子，但它们似乎仅限于两个数字，因为我的程序需要使用的数量与原始数量的总和要相等。
我看了一些关于0/1背包问题的视频。我努力将相同的概念应用于自己的程序，因为问题完全不同。他们可以放进袋子的东西可以减轻体重和利润。
这已经使我的大脑受伤了几个小时，如果有人甚至可以将我指向正确的方向，我将不胜感激，谢谢：）
from math import sqrt
def decompose(n):
lst = []
sets = []
temp = []
perm = {}
out = []
for i in range (n):
lst.append(i**2)
for i in lst:
for x in sets:
temp.append(i + x)
perm[i + x] = (i, x)
for x in temp:
if x not in sets:
sets.append(x)
if i not in sets:
sets.append(i)
temp = []
if n**2 not in perm.keys():
return None
for i in perm[n**2]:
if str(i).isdigit():
out.append(i)
if i == ' ':
out.append(i)
for i in out:
if i not in lst:
out.remove(i)
for i in perm[i]:
if str(i).isdigit():
out.append(i)
if i == ' ':
out.append(i)
out.sort()
return [sqrt(i) for i in out]
这里是一个递归程序，用于查找分解。速度可能不是最佳的。当然，这对于搜索大范围的输入不是最佳的，因为当前方法不缓存中间结果。
def find_decomposition(n, k=1, uptonow=0, used=[]):
# first try without k
if k < n-1:
decomp = find_decomposition(n, k+1, uptonow, used)
if decomp is not None:
return decomp
# now try including k
used_with_k = used + [k]
if uptonow + k * k == n * n:
return used_with_k
elif k < n-1 and uptonow + k * k + (k+1)*(k+1) <= n * n:
# no need to try k if k doesn't fit together with at least one higher number
return find_decomposition(n, k+1, uptonow+k*k, used_with_k)
return None
for n in range(5,1001):
print(n, find_decomposition(n))
输出：
5 [3, 4]
6 None
7 [2, 3, 6]
8 None
9 [2, 4, 5, 6]
10 [6, 8]
11 [2, 6, 9]
12 [1, 2, 3, 7, 9]
13 [5, 12]
14 [4, 6, 12]
15 [9, 12]
16 [3, 4, 5, 6, 7, 11]
...
PS：此链接包含有关一个相关问题的代码，但是可以重复平方：https://www.geeksforgeeks.org/minimum-number-of-squares-whose-sum-equals-to-given-number-n/
这个太大了，无法发表评论，所以我将其放在此处作为答案：
恰好是0/1背包或“找零问题”（en.wikipedia.org/wiki/Change-making_problem）。您的目标是赚25美分（如果n = 5）。您的“硬币”是1美分，4美分，9美分，16美分，等等。我假设由于您使用的是0/1背包，因此无法重复使用同一枚硬币（如果可以重复使用同一枚硬币硬币，问题要简单得多。
有两种方法可以解决这样的动态编程问题。它们都以自己的方式直观，但是目前您可能更直观。
首先是记忆（自上而下）。在此处为decompose编写递归函数，但将对decompose的每次调用的结果缓存起来。此处的递归公式将类似于
decompose_cache = dictionary that stores results of calls to decompose
def decompose(n = 25, coins_to_use={1,4,9,16}):
if (n, coins_to_use) in decompose_cache:
return decompose_cache[(n, coins_to_use)]
biggest_coin = max(coins_to_use)
other_coins = coins_to_use - {biggest_coin}
decomposition_with_biggest_coin = decompose(n-biggest_coin, other_coins)
decomposition_without_biggest_coin = decompose(n, other_coins)
ans = decomposition_with_biggest_coin or decomposition_without_biggest_coin
decompose_cache[(n, coins_to_use)] = ans
return ans
print(decompose(25, {1,4,9,16}))
也就是说，要确定我们是否可以使用{1,4,9,16}赚取25美分，我们只需要检查我们是否可以使用{1,4,9}赚取25美分，或者我们可以赚取9美分（25-16）使用{1,4,9}。如果不缓存每个调用的结果，则此递归定义将导致类似O(n^n)函数调用的操作，但是由于我们缓存了结果，因此我们最多只能对某些（目标，硬币）对进行一次计算。有n ^ 2个可能的目标，有n组可能的硬币，因此，有n ^ 2 * n对，因此有O(n^2 * n = n^3)个函数调用。
第二种方法是动态编程（称为自下而上）。 （我个人认为这比较简单，并且不会在python中遇到最大递归深度问题）
这是您从空的基本情况开始填充表的位置，在该情况下，可以通过查看已经填写的条目的值来计算表中条目的值。我们可以将表格称为“ DP”。在这里，如果您可以仅使用前k个“硬币”（其中第一个硬币为1，第二个硬币为4，等等）可以求和为n的值，则可以构建一个表，其中DP [n] [k]为真）。
我们计算表中单元格值的方法是：DP[n][k] = DP[n - kth coin][k-1] OR DP[n][k-1]
逻辑与上述相同：当且仅当我们可以使用{进行1分（5-4）的改变，我们可以用硬币{1,4}（前两个硬币）进行5分的改变。 1}（第一个硬币），或者我们可以使用{1}兑换5美分。因此，DP [5] [2] = DP [1] [1]或DP [5] [1]。同样，此表有n ^ 3个条目。您可以从[0] [0]到[0] [5]逐行填充，然后从[0] [...]到[25] [...]每行填充，答案将是在[25] [5]中。