โปรแกรมหาผลรวมที่ใกล้เคียงที่สุดใน Python

สมมติว่าเรามีจำนวนอาร์เรย์และเป้าหมายค่าอื่น เราต้องการเลือกลำดับรองของ 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

• จัดเรียง nums ตามค่า -ve หลังจากได้รับค่าสัมบูรณ์ของ x

• neg :=สร้างอาร์เรย์ขนาด n+1 และเติม 0

• pos :=สร้างอาร์เรย์ขนาด n+1 และเติม 0

• สำหรับฉันในช่วง n-1 ถึง 0, ลดลง 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 หรือ เป้าหมาย + ans

  • คืนค่าเท็จ

• คืนค่า True

• จากวิธีหลัก ให้ทำดังนี้

• สำหรับฉันอยู่ในช่วง 0 ถึง n - 1 ทำ

  • sl :=รายการของ x สำหรับ x ทั้งหมดใน s เมื่อ check(x+neg[i], x+pos[i] is true]

  • ถ้าขนาดของ sl เท่ากับ 0 แล้ว

    • ออกจากวง

  • s :=ชุดใหม่จาก sl

  • สำหรับแต่ละ x ใน sl ทำ

    • y :=x + nums[i]

    • ถ้า |y - เป้าหมาย|

      • ans :=|y - เป้าหมาย|

    • ถ้า ans เหมือนกับ 0 แล้ว

      • คืนค่า 0

    • ใส่ y ลงใน s

• กลับมาอีกครั้ง

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