पायथन में निकटतम सबसीक्वेंस योग खोजने का प्रोग्राम

मान लीजिए हमारे पास एक सरणी nums और एक अन्य मान goal है। हम nums का एक सबसीक्वेंस चुनना चाहते हैं ताकि उसके तत्वों का योग goal के निकटतम हो। दूसरे शब्दों में, यदि सबसीक्वेंस के तत्वों का योग 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 को x के निरपेक्ष मान के नकारात्मक मान के आधार पर सॉर्ट करें
neg := n+1 आकार की एक सरणी बनाएं और 0 से भरें
pos := n+1 आकार की एक सरणी बनाएं और 0 से भरें
i के लिए n-1 से 0 तक घटाते हुए लूप चलाएं
- यदि 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 := |goal|
s := एक नया सेट और इसमें 0 डालें
check() फंक्शन परिभाषित करें। यह a, b लेगा
यदि b < goal - ans या goal + ans < a, तो False लौटाएं
True लौटाएं
मुख्य विधि से, निम्न करें
i के लिए 0 से n-1 तक लूप चलाएं
- sl := s में सभी x की सूची जब check(x+neg[i], x+pos[i] सत्य है]
- यदि sl का आकार 0 के बराबर है, तो लूप से बाहर निकलें
- s := sl से एक नया सेट
- sl में प्रत्येक x के लिए
  - y := x + nums[i]
  - यदि |y - goal| < ans, तो ans := |y - goal|
  - यदि 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]]