我有以下代码执行速度太慢。这个想法类似于 0/1 背包问题,你有一个给定的整数 n,你必须找到 1 到 n - 1 范围内的数字,这些数字的平方加起来等于 n 的平方。
例如,如果 n 是 5,那么它应该输出 3 , 4 因为 3 ** 2 和 4 ** 2 = (25 or 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]
最佳答案
这对于评论来说太大了,所以我把它放在这里作为答案:
它恰好是 0/1 背包或“硬币找零问题”(en.wikipedia.org/wiki/Change-making_problem)。您的目标是赚取 25 美分(如果 n = 5)。你的“硬币”是 1 美分、4 美分、9 美分、16 美分等。我假设因为你正在看 0/1 背包,你不能重复使用相同的硬币(如果你可以重复使用相同的硬币,问题就简单多了)。
有两种解决此类动态规划问题的方法。它们都以自己的方式直观,但目前您可能更直观。
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)
的函数调用,但由于我们缓存了结果,我们只为some (goal, coins) 最多配对一次。有 n^2 个可能的目标,n 个可能的硬币组,所以有 n^2 * n 对,所以有 O(n^2 * n = n^3)
函数调用.
2.
第二种方法是动态规划(称为自下而上)。 (我个人认为这样想起来更简单,不会在python中遇到最大递归深度问题)
这是您填写表格的地方,从空的基本情况开始,表格中条目的值可以通过查看已填写条目的值来计算。我们可以称这个表为“DP”。
在这里,我们可以构建一个表,其中 DP[n][k] 为真,如果您可以仅使用前 k 个“硬币”(其中第一个硬币为 1,第二个硬币为 4,等等)求和为 n 的值).
我们可以计算表格中单元格值的方法是:
DP[n][k] = DP[n - kth coin][k-1] OR DP[n][k-1]
逻辑与上面相同:我们可以找零 5 美分,硬币 {1,4}(前两个硬币)当且仅当我们可以找零 1 美分(5-4)时使用{1}(第一枚硬币)或者我们是否可以使用 {1} 找零 5 美分。所以,DP[5][2] = DP[1][1] 或 DP[5][1]。 同样,该表有 n^3 个条目。您可以从 [0][0] 到 [0][5] 逐行填写,然后从 [0][...] 到 [25][...] 逐行填写,答案将在 [25][5] 中。
关于python - 用 Python 简化的 0/1 背包问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59014861/