Pythonで最も近いサブシーケンスの合計を見つけるプログラム

配列numsと別の値の目標があるとします。要素の合計が目標に最も近くなるように、numsのサブシーケンスを選択する必要があります。つまり、サブシーケンスの要素の合計がsの場合、絶対差| s--goal|を最小化する必要があります。

したがって、| s --goal |の可能な最小値を見つける必要があります。したがって、入力がnums =[8、-8,16、-1]goal =-3の場合、出力は2になります。サブシーケンス[8、-8、-1]、合計-1。絶対差は|-1-（-3）|です。 =abs（2）=2、これは最小値です。

これを解決するには、次の手順に従います-

• n：=numsのサイズ

• xの絶対値を取得した後、-ve値に基づいて数値を並べ替える

• neg：=サイズn + 1の配列を作成し、0で埋めます

• pos：=サイズn + 1の配列を作成し、0で埋めます

• n-1から0の範囲のiの場合、1ずつ減らします。

  • nums [i] <0の場合、

    • neg [i]：=neg [i + 1] + nums [i]

    • pos [i]：=pos [i + 1]

  • それ以外の場合

    • pos [i]：=pos [i + 1] + nums [i]

    • neg [i]：=neg [i + 1]

• ans：=|目標|

• s：=新しいセットとそれに0を挿入

• 関数check（）を定義します。これにはa、bが必要です

• b<目標-ansまたはgoal+ans

  • Falseを返す

• Trueを返す

• メインの方法から、次のようにします

• 0からn-1の範囲のiの場合、実行

  • sl：=check（x + neg [i]、x + pos [i] true]

    の場合のs内のすべてのxのxのリスト

  • slのサイズが0と同じ場合、

    • ループから出てきます

  • s：=slからの新しいセット

  • slのxごとに、実行します

    • y：=x + nums [i]

    • |y-ゴール|の場合

      • ans：=|y-目標|

    • ansが0と同じ場合、

      • 0を返す

    • yをsに挿入します

• ansを返す

例

理解を深めるために、次の実装を見てみましょう

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