当前位置: 首页 > 面试题库 >

查找列表中哪个数字加起来等于某个数字的算法

和光启
2023-03-14
问题内容

我有一个数字清单。我也有一定数目
该总和由我列表中的几个数字得出(我可能/可能不知道它是由多少个数字组成的)。是否有一种快速算法来获取可能的数字列表?用Python编写会很棒,但是伪html" target="_blank">代码也很好。(除Python:P之外,我什么都看不到)

list = [1,2,3,10]
sum = 12
result = [2,10]

注意:
我确实知道算法,可以从大小为n的列表中找到哪些数字总和为另一个数字(但是我无法读取C#,也无法检查它是否满足我的需求。我在Linux上,尝试使用单声道,但我遇到错误,我不知道如何工作C#:(而且


问题答案:

该问题简化为0-1背包问题,您尝试在其中找到具有精确总和的集合。解决方案取决于约束条件,一般情况下,此问题是NP-
Complete。

但是,如果最大搜索总和(称为S)不太高,则可以使用动态编程解决问题。我将使用递归函数和备忘录对其进行解释,这比自下而上的方法更容易理解。

让我们对一个函数进行编码f(v, i, S),以使其返回v[i:]恰好等于的子集数S。为了递归地解决它,首先我们必须分析基数(即:v[i:]为空):

  • S == 0:的唯一子集的[]总和为0,因此它是有效子集。因此,该函数应返回1。

  • S!= 0:由于的唯一子集的[]总和为0,因此没有有效的子集。因此,该函数应返回0。

然后,让我们分析递归情况(即:v[i:]不为空)。有两种选择:将数字包括v[i]在当前子集中,或不包括。如果包含v[i],那么我们正在寻找具有sum的子集S - v[i],否则,我们仍在寻找具有sum的子集S。该功能f可以通过以下方式实现:

def f(v, i, S):
  if i >= len(v): return 1 if S == 0 else 0
  count = f(v, i + 1, S)
  count += f(v, i + 1, S - v[i])
  return count

v = [1, 2, 3, 10]
sum = 12
print(f(v, 0, sum))

通过检查f(v, 0, S) > 0,您可以知道是否有解决问题的方法。但是,此代码太慢,每个递归调用都产生两个新的调用,从而导致O(2 ^
n)算法。现在,我们可以应用备忘录以使其在时间O(n * S)中运行,如果S不是太大,它将更快:

def f(v, i, S, memo):
  if i >= len(v): return 1 if S == 0 else 0
  if (i, S) not in memo:  # <-- Check if value has not been calculated.
    count = f(v, i + 1, S, memo)
    count += f(v, i + 1, S - v[i], memo)
    memo[(i, S)] = count  # <-- Memoize calculated result.
  return memo[(i, S)]     # <-- Return memoized value.

v = [1, 2, 3, 10]
sum = 12
memo = dict()
print(f(v, 0, sum, memo))

现在,可以对g返回一个总和的子集的函数进行编码S。为此,仅在至少有一个包含元素的解决方案时才添加元素就足够了:

def f(v, i, S, memo):
  # ... same as before ...

def g(v, S, memo):
  subset = []
  for i, x in enumerate(v):
    # Check if there is still a solution if we include v[i]
    if f(v, i + 1, S - x, memo) > 0:
      subset.append(x)
      S -= x
  return subset

v = [1, 2, 3, 10]
sum = 12
memo = dict()
if f(v, 0, sum, memo) == 0: print("There are no valid subsets.")
else: print(g(v, sum, memo))

免责声明:此解决方案表示[10,10]有两个子集,总和为10。这是因为它假定前十个与后十个不同。可以将算法固定为假定两个十个相等(并因此回答一个),但这有点复杂。



 类似资料: