在Python中查找最接近的子序列总和的程序

• Z时代
• 2024-01-10
• 分类：综合

假设我们有一个数组 nums 和另一个值目标。我们想要选择一个 nums 子序列，使其元素的总和最接近目标。所以换句话说，如果子序列元素的总和是 s，那么我们要最小化绝对差 |s -goal|。

所以我们必须找到|s -目标|的最小可能值。因此，如果输入类似于 nums = [8,-8,16,-1] 目标 = -3，那么输出将为 2，因为选择子序列 [8,-8,-1]，总和为 - 1. 绝对差为|-1 - (-3)| = abs(2) = 2，这是最小值。

示例

让我们看下面的实现来更好地理解

from collections import Counter
def solve(nums, goal):
   n = len(nums)
   nums.sort(key=lambda x: -abs(x))
   neg = [0 for _ in range(n+1)]
   pos = [0 for _ in range(n+1)]
   for i in range(n-1, -1, -1):
      if nums[i] < 0:
         neg[i] = neg[i+1] + nums[i]
         pos[i] = pos[i+1]
      else:
         pos[i] = pos[i+1] + nums[i]
         neg[i] = neg[i+1]
   ans = abs(goal)
   s = set([0])
   def check(a, b):
      if b < goal - ans or goal + ans < a:
         return False
      return True
   for i in range(n):
      sl = [x for x in s if check(x+neg[i], x+pos[i])]
      if len(sl) == 0:
         break
      s = set(sl)
      for x in sl:
         y = x + nums[i]
         if abs(y - goal) < ans:
            ans = abs(y - goal)
         if ans == 0:
            return 0
         s.add(y)
   return ans
nums = [8,-8,16,-1]
goal = -3
print(solve(nums, goal))

输入

[0,1,2,3,4], [[3,1],[1,3],[5,6]]

2

以上是 在Python中查找最接近的子序列总和的程序 的全部内容， 来源链接： utcz.com/z/358620.html