Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

सभी कार्यों को पूरा करने के लिए न्यूनतम समय ज्ञात करने का पायथन प्रोग्राम


मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है जहां प्रत्येक मान एक कार्य को पूरा करने में लगने वाली समय इकाई निर्धारित करता है। हम किसी भी गैर-लगातार कार्यों को छोड़ सकते हैं, हमें सभी कार्यों को पूरा करने में लगने वाला न्यूनतम समय ढूंढना है।

उदाहरण के लिए, यदि इनपुट nums = [11, 6, 8, 16] है, तो आउटपुट 14 होगा, क्योंकि हम पहले और अंतिम कार्यों को छोड़ सकते हैं।

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:

  • n := nums का आकार
  • table := एक n x 2 मैट्रिक्स बनाएं और इसे 0 से भरें
  • table[0, 0] := 0
  • table[0, 1] := nums[0]
  • i को 1 से n - 1 तक के लिए, करें
    • table[i, 0] := table[i - 1, 1]
    • table[i, 1] = (table[i - 1, 0] और table[i - 1][1] में से न्यूनतम) + nums[i]
  • table पंक्ति [n - 1] का न्यूनतम लौटाएं

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

उदाहरण

class Solution:
    def solve(self, nums):
        n = len(nums)
        table = [[0] * 2 for _ in range(n)]
        table[0][0] = 0
        table[0][1] = nums[0]
        for i in range(1, n):
            table[i][0] = table[i - 1][1]
            table[i][1] = min(table[i - 1][0], table[i - 1][1]) + nums[i]
        return min(table[n - 1])

ob = Solution()
nums = [11, 6, 8, 16]
print(ob.solve(nums))

इनपुट

[11, 6, 8, 16]

आउटपुट

14

  1. Python में सभी बिंदुओं को जोड़ने की न्यूनतम लागत खोजने का प्रोग्राम Python में सभी बिंदुओं को जोड़ने की न्यूनतम लागत खोजने का प्रोग्राम

    मान लीजिए हमारे पास points नामक एक ऐरे है जिसमें कुछ पॉइंट्स (x, y) के रूप में हैं। अब दो पॉइंट्स (xi, yi) और (xj, yj) को जोड़ने की लागत उनके बीच की मैनहट्टन दूरी है, सूत्र है |xi - xj| + |yi - yj|। हमें सभी पॉइंट्स को जोड़ने की न्यूनतम लागत ढूंढनी है। उदाहरण के लिए, यदि इनपुट है points = [(0,0),(

  1. Python से DAG में सभी नोड्स तक पहुंचने के लिए मिनिमम वर्टेक्स कैसे ढूंढें? Python से DAG में सभी नोड्स तक पहुंचने के लिए मिनिमम वर्टेक्स कैसे ढूंढें?

    डायरेक्टेड एसाइक्लिक ग्राफ (DAG) में जिन वर्टेक्सेज़ का इन-डिग्री 0 है, उनसे सभी नोड्स पहुंचे जा सकते हैं। एल्गोरिदम सभी नोड्स का सेट बनाएं (0 से n-1)। सभी एजेज़ के डेस्टिनेशन नोड्स (v) का सेट बनाएं। सोर्स नोड्स = सभी नोड्स - डेस्टिनेशन नोड्स (यानी इन-डिग्री 0 वाले)। यही मिनिमम वर्टेक्स सेट है। उद

  1. - Python में दिए गए प्रतिबंधों के साथ सभी कार्यों को पूरा करने का न्यूनतम समय ढूंढना

    मान लीजिए हमारे पास अलग-अलग समय आवश्यकताओं वाले कार्यों की एक सरणी है, k अलग-अलग व्यक्ति हैं जिन्हें कार्य सौंपे जाने हैं और हमारे पास यह भी है कि एक असाइनी को कार्य की एक इकाई करने में कितना समय t लगता है। हमें निम्नलिखित प्रतिबंधों के साथ सभी कार्यों को पूरा करने का न्यूनतम समय ढूंढना है। एक असाइ