পাইথনে নিকটতম পরবর্তী যোগফল খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের একটি অ্যারে সংখ্যা এবং আরেকটি মান লক্ষ্য রয়েছে। আমরা সংখ্যার একটি পরের অংশ নির্বাচন করতে চাই যাতে এর উপাদানগুলির যোগফল লক্ষ্যের সবচেয়ে কাছাকাছি হয়। তাই অন্য কথায়, যদি পরের উপাদানগুলির যোগফল s হয়, তাহলে আমরা পরম পার্থক্য |s - লক্ষ্য|কে কমিয়ে আনতে চাই।

তাই আমাদের |s - লক্ষ্য পরবর্তী [8,-8,-1], -1 এর যোগফল সহ। পরম পার্থক্য হল |-1 - (-3)| =abs(2) =2, এটি সর্বনিম্ন।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n :=সংখ্যার আকার

• x

  এর পরম মান পাওয়ার পর -ve মানের উপর ভিত্তি করে সংখ্যা সাজান

• neg :=n+1 আকারের একটি অ্যারে তৈরি করুন এবং 0

  দিয়ে পূরণ করুন

• pos :=n+1 আকারের একটি অ্যারে তৈরি করুন এবং 0

  দিয়ে পূরণ করুন

• n-1 থেকে 0 রেঞ্জে i এর জন্য, 1 দ্বারা হ্রাস করুন, করুন

  • যদি সংখ্যা [i] <0, তারপর

    • neg[i] :=neg[i+1] + সংখ্যা[i]

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

  • অন্যথায়,

    • pos[i] :=pos[i+1] + সংখ্যা[i]

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

• উত্তর :=|লক্ষ্য|

• s :=একটি নতুন সেট এবং এতে 0 ঢোকান

• একটি ফাংশন চেক () সংজ্ঞায়িত করুন। এটি একটি, b

  লাগবে৷

• যদি b <লক্ষ্য - ans বা লক্ষ্য + ans

  • রিটার্ন ফলস

• রিটার্ন ট্রু

• মূল পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন

• আমি 0 থেকে n - 1 রেঞ্জের জন্য, করুন

  • sl :=সব x-এর জন্য x-এর একটি তালিকা যখন চেক (x+neg[i], x+pos[i] সত্য]

  • যদি sl এর আকার 0 এর মতো হয়, তাহলে

    • লুপ থেকে বেরিয়ে আসুন

  • s :=sl

    থেকে একটি নতুন সেট

  • এসএল-এ প্রতিটি x এর জন্য, করুন

    • y :=x + সংখ্যা[i]

    • যদি |y - লক্ষ্য| <উত্তর, তারপর

      • উত্তর :=|y - লক্ষ্য|

    • যদি উত্তর 0 এর মত হয়, তাহলে

      • রিটার্ন 0

    • s

      -এ y ঢোকান

• উত্তর ফেরত দিন

উদাহরণ

আসুন আরও ভালভাবে বোঝার জন্য নিম্নলিখিত বাস্তবায়ন দেখি

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