算法来查找号码列表中总结到一定数量 [英] Algorithm to find which number in a list sum up to a certain number

问题描述

予有号码的列表。我也有一定的总和。该款项是从我的名单上的几个号码的（我可能/可能不知道它有多少人数从制造）。是否有一个快速的算法来获得尽可能号码列表？用Python编写的将是巨大的，但伪code的好太多。 （我还不能读什么其他比Python：P）

I have a list of numbers. I also have a certain sum. The sum is made from a few numbers from my list (I may/may not know how many numbers it's made from). Is there a fast algorithm to get a list of possible numbers? Written in Python would be great, but pseudo-code's good too. (I can't yet read anything other than Python :P )

示例

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

注意：我知道的<一href="http://stackoverflow.com/questions/83547/algorithm-to-find-which-numbers-from-a-list-of-size-n-sum-to-another-number">http://stackoverflow.com/questions/83547/algorithm-to-find-which-numbers-from-a-list-of-size-n-sum-to-another-number （但我无法读取C＃和我无法判断是否适合我的需要。我在Linux上，我试着用单声道，但我得到的错误，我无法弄清楚如何工作的C＃:(
和的我知道 http://stackoverflow.com/questions/403865 的（但它似乎是相当低效的。我并不需要所有的组合。）

NOTE: I do know of http://stackoverflow.com/questions/83547/algorithm-to-find-which-numbers-from-a-list-of-size-n-sum-to-another-number (but I cannot read C# and I'm unable to check if it works for my needs. I'm on Linux and I tried using Mono but I get errors and I can't figure out how to work C# :(
AND I do know of http://stackoverflow.com/questions/403865 (but it seems to be fairly inefficient. I don't need all combinations.)

推荐答案

这个问题降低到 0-1背包问题，在那里你正在努力寻找一组与一个确切的总和。该解决方案取决于约束，在一般情况下，这问题是NP完全

This problem reduces to the 0-1 Knapsack Problem, where you are trying to find a set with an exact sum. The solution depends on the constraints, in the general case this problem is NP-Complete.

但是，如果最大的搜索总和（我们称之为取值）不太高，那么你可以使用动态规划解决的问题。我会用递归函数和记忆化，哪一个更容易理解比自下而上的方法解释。

However, if the maximum search sum (let's call it S) is not too high, then you can solve the problem using dynamic programming. I will explain it using a recursive function and memoization, which is easier to understand than a bottom-up approach.

让我们codeA功能 F（V，I，S），这样它会返回子集的个数v [我： ] 的款项完全以取值。为了解决这个问题递归，首先我们要分析的基础（如： v [电流：] 为空）：

Let's code a function f(v, i, S), such that it returns the number of subsets in v[i:] that sums exactly to S. To solve it recursively, first we have to analyze the base (i.e.: v[i:] is empty):

• 取值== 0：的唯一子集[] 的总和0，所以它是一个有效的子集。正因为如此，该函数应该返回1

• S == 0: The only subset of [] has sum 0, so it is a valid subset. Because of this, the function should return 1.

S = 0：当的唯一子集[] 的总和0，没有有效的子集。正因为如此，该函数将返回0

S != 0: As the only subset of [] has sum 0, there is not a valid subset. Because of this, the function should return 0.

那么，让我们来分析递归的情况下（即： v [电流：] 不为空）。有两种选择：包括 v [电流] 在当前的子集数，或者不包括它。如果包括 v [电流] ，有一笔那么我们正在寻找的子集的S - v [电流] ，否则我们仍在寻找与金额取值子集。函数 F 可能会以如下方式实现的：

Then, let's analyze the recursive case (i.e.: v[i:] is not empty). There are two choices: include the number v[i] in the current subset, or not include it. If we include v[i], then we are looking subsets that have sum S - v[i], otherwise, we are still looking for subsets with sum S. The function f might be implemented in the following way:

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）＆GT; 0 ，你就可以知道是否有解决您的问题。然而，这code是太慢了，每次递归调用会生成两个新的呼叫，从而导致了O（2 ^ n）的算法。现在，我们可以应用记忆化，以使其在时间O（N * S），这是更快，如果<$ C运行$ C>取值不是太大：

By checking f(v, 0, S) > 0, you can know if there is a solution to your problem. However, this code is too slow, each recursive call spawns two new calls, which leads to an O(2^n) algorithm. Now, we can apply memoization to make it run in time O(n*S), which is faster if S is not too big:

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))

现在，就可以codeA功能先按g 返回一个子集中的款项取值。要做到这一点，它足以添加元素仅当存在至少一个解决方案，包括它们：

Now, it is possible to code a function g that returns one subset that sums S. To do this, it is enough to add elements only if there is at least one solution including them:

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。这是因为它假设前十个不同的是向第二10。该算法可以被固定到假定这两个数十相等（并且因此回答一个），但是这是一个比较复杂。

Disclaimer: This solution says there are two subsets of [10, 10] that sums 10. This is because it assumes that the first ten is different to the second ten. The algorithm can be fixed to assume that both tens are equal (and thus answer one), but that is a bit more complicated.

这篇关于算法来查找号码列表中总结到一定数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！