0/1 背包问题在 Python 中得到简化

Question

我的以下代码执行速度太慢。这个想法类似于 0/1 背包问题，你有一个给定的整数 n，你必须找到 1 到 n - 1 范围内的数字，这些数字的平方加起来等于 n 的平方。

例如，如果 n 是 5，那么它应该输出 3 , 4 因为 3 ** 2 和 4 ** 2 = (25 or 5 ** 2)。我一直在努力了解如何使它更有效率，并想知道用于提高此类程序效率的概念。

一些其他示例：n = 8 [None] 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]

Answer 1

这里是一个寻找分解的递归程序。速度可能不是最佳的。当然，它不是搜索大范围输入的最佳选择，因为当前方法不缓存中间结果。

在此版本的函数中，find_decomposition(n, k, uptonow, used) 尝试仅使用从 k 到 n-1，而我们已经使用了 used 组数字，这些数字给出了 uptonow 的部分和。该函数递归地尝试 2 种可能性：要么解决方案包含 k 本身，要么不包含 k。首先尝试一种可能性，如果可行，return它。如果没有，请尝试其他方式。因此，首先尝试不使用 k 的解决方案。如果没有成功，请进行快速测试以查看仅使用 k 是否可以提供解决方案。如果这也没有解决，递归地尝试使用 k 的解决方案，因此 used 数字集现在包括 k 其中总和 uptonow ]需要增加k².

可以想到很多变化：

而不是运行从 1 到 n-1，k 可以按相反的顺序运行。小心 if-test 的测试条件。
与其先尝试不包含 k 的解决方案，不如先尝试包含 k 的解决方案。

注意对于大n，函数可以运行进入最大递归深度。例如。当 n=1000 时，大约有 2⁹⁹⁹ 个可能的数字子集要被递归检查。这可能导致 999 级深度的递归，这在某些时候对于 Python 解释器来说太多了，无法处理。

可能首先用完高数字的方法可能是有益的，因为它可以快速减少需要填补的差距。幸运的是，对于大量存在许多可能的解决方案，因此可以快速找到解决方案。请注意，在@Kevin Wang 描述的一般背包问题中，如果不存在解决方案，则任何具有 999 数字的方法都将花费太长时间才能完成。

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：此 link 包含有关相关问题的代码，但方块可以重复： https://www.geeksforgeeks.org/minimum-number-of-squares-whose-sum-equals-to-given-number-n/

Answer 2

这篇评论太大了，所以我把它放在这里作为答案：

恰好是 0/1 背包或“硬币找零问题”(en.wikipedia.org/wiki/Change-making_problem)。您的目标是赚取 25 美分（如果 n = 5）。你的“硬币”是 1 美分、4 美分、9 美分、16 美分等。我假设因为你正在看 0/1 背包，你不能重复使用相同的硬币（如果你可以重复使用相同的coin，问题就简单多了）。

有两种解决此类动态规划问题的方法。它们都以自己的方式直观，但目前您可能更直观。

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 美分，或者如果我们可以使用 {1,4,9} 赚取 9 美分 (25 - 16)。这个递归定义，如果我们不缓存每次调用的结果，将导致类似于 O(n^n) 函数调用，但由于我们缓存了结果，我们只对某些（目标，硬币）对进行计算大多数一次。有 n^2 个可能的目标，n 个可能的硬币组，所以有 n^2 * n 对，所以有 O(n^2 * n = n^3) 次函数调用。

2.

第二种方法是动态规划（称为自下而上）。（我个人认为这个比较简单，你不会运行进入python中的最大递归深度问题）

这是你填写一个 table 的地方，从空的基本情况开始，其中 table 中的一个条目的值可以通过查看已经存在的条目的值来计算填写。我们可以称table为“DP”。
在这里，我们可以构建一个 table，其中 DP[n][k] 为真，如果您可以仅使用前 k 个“硬币”（其中第一个硬币为 1，第二个硬币）求和为 n 的值是 4，等等）。

我们计算 table 中单元格值的方法是：
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]。同样，此 table 有 n^3 个条目。您可以从 [0][0] 到 [0][5] 逐行填写，然后从 [0][...] 到 [25][...] 逐行填写，答案将在 [25][5].

0/1 背包问题在 Python 中得到简化

0/1 Knapsack Problem Simplified in Python

python

performance

knapsack-problem

processing-efficiency

python-3.x

1.

2.