Python 列表中的一个或多个元素的总和或值等于给定条件

Question

我正在制作一种算法，可以从列表中获取相等的元素或元素列表，或者其总和等于给定数字。

list1 = [1,1, 1, 1,2,3,3,4,7,8,9, 45, 67, 98] (Sum up to 3)

list2 = [5,40, 70, 120, 150]      (Sum up to 130)

来自 list1 想要总和为 3 的元素，但我的目标是查找列表中是否存在像 3 这样的确切数字，然后选择它，否则选择总和为 3 的其他数字.

从 list2 我需要一个等于 130 的值或总和为 130 的元素，如您所见，没有匹配的值，因此我需要选择一个与其最匹配的元素(例如 150)然后将其保存到另一个数组中。注意:请注意，并不是说对要组合的元素没有限制，只要元素总数达到所需的数量，但我更愿意先查看列表，看看是否有确切的数字匹配。

下面是我正在使用的代码，但我只能得到总结的值，我需要帮助来解决更复杂的解决方案。

class select_pair():
  def __init__(self, l, target):
  self.__l = l
  self.__target = target
  if not isinstance(l, list):
  raise TypeError("it must be a list")
  elif not isinstance(target, int):
  raise TypeError("it must be an integer")
  for i in range(len(l)-1):

  if l[i] == target:  
    print("from 1st index1:{}".format(i))
    break
  elif l[i]+l[i+1] == target:
   print("from second index1:{}, index2:{}".format(i+1, i+2))
   break


p = select_pair(list1,3)
p = select_pair(list2,130)

Answer 1

可能没有更好的方法来测试列表中 1、2、3、... 元素的所有组合是否与给定的目标总和匹配。但是，您可以通过使用元组(与目标的差异，元素数量) 作为要最小化的键来组合三种情况(完全匹配、匹配总和和最近总和)。

from itertools import combinations    
def combs(lst, n):
    return (c for k in range(1, n+1) for c in combinations(lst, k))

def best_match(lst, target, n=3):
    return min(combs(lst, n), key=lambda c: (abs(target - sum(c)), len(c)))

list1 = [1,1, 1, 1,2,3,3,4,7,8,9, 45, 67, 98]
list2 = [5,40, 70, 120, 150]
print(best_match(list1, 3))   # (3,)
print(best_match(list2, 130)) # (5, 120)

这里，n 是要组合的元素的最大数量。当然，您也可以使用高于 3 的值，但对于较长的列表，这意味着需要比较的元素要多很多。另请注意，如果找到完美匹配，该函数不会提前停止，尽管这可以使用常规循环而不是 min 来实现。

def best_match_stop_early(lst, target, n=3):
    best = None
    for c in combs(lst, n):
        v = (abs(target - sum(c)), len(c), c)
        if best is None or v < best:
            best = v
            if v[0] == 0:
                return v[2]
    return best[2]

类似地，您可以调整 combs 函数，使其不仅生成所有组合，还可以提前中止，例如如果组合的总和已经大于目标总和，那么向该组合添加更多数字不会使其变得更好 - 但其他更长的组合可能会更好。但是，这仅适用于该特定目标函数，并且仅当列表中没有负数时才有效。