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

Python में समान संख्या में लोगों को दो अलग-अलग शहरों में भेजने की न्यूनतम लागत खोजने का प्रोग्राम

मान लीजिए हमारे पास costs नामक एक सूची है। जहां costs[i] में [c1, c2] होता है जो दर्शाता है कि व्यक्ति i के लिए शहर 0 तक पहुंचने की लागत c1 है और शहर 1 तक पहुंचने की लागत c2 है। हम चाहते हैं कि समान संख्या में लोग शहर 0 और शहर 1 जाएं, हमें आवश्यक न्यूनतम लागत ज्ञात करनी है।

इसलिए, यदि इनपुट है costs = [[2, 6], [10, 3], [4, 9], [5, 8]], तो आउटपुट 17 होगा, क्योंकि व्यक्ति 0 और 2 शहर 0 जाएंगे और व्यक्ति 1 और 3 शहर 1, तो शहर 0 के लिए लागत 2+4=6 है, और शहर 1 के लिए लागत 8+3=11 है, कुल 17।

हल करने का दृष्टिकोण

  • s := 0
  • a := एक नई सूची
  • costs में प्रत्येक जोड़ी (x, y) के लिए, करें:
    • s := s + x
    • a के अंत में (y - x) डालें
  • सूची a को सॉर्ट करें
  • 0 से floor(len(a)/2) - 1 तक i के लिए, करें:
    • s := s + a[i]
  • s लौटाएं

उदाहरण

def solve(costs):
    s = 0
    a = []
    for x, y in costs:
        s += x
        a += (y - x,)
    a.sort()
    for i in range(len(a) // 2):
        s += a[i]
    return s

costs = [[2, 6], [10, 3], [4, 9], [5, 8]]
print(solve(costs))

इनपुट

[[2, 6], [10, 3], [4, 9], [5, 8]]

आउटपुट

17
  1. पायथन में छड़ी काटने की न्यूनतम लागत ज्ञात करने का प्रोग्राम पायथन में छड़ी काटने की न्यूनतम लागत ज्ञात करने का प्रोग्राम

    मान लीजिए हमारे पास एक मान n और cuts नामक एक सरणी है। मान लीजिए n इकाई लंबाई की एक लकड़ी की छड़ी है। छड़ी 0 से n तक लेबल की गई है। यहां cuts[i] एक स्थिति दर्शाता है जहां हम काट सकते हैं। हमें कटौती क्रम में करनी चाहिए, लेकिन हम कटौती के क्रम को अपनी इच्छानुसार बदल सकते हैं। यहां एक कटौती की लागत का

  1. - Python में घरों को रंगने की न्यूनतम लागत खोजने का प्रोग्राम

    मान लीजिए आकार m का एक ऐरे है, जो एक छोटे शहर में m घरों को दर्शाता है, प्रत्येक घर को n रंगों में से एक से रंगा जाना चाहिए (रंग 1 से n तक लेबल किए गए हैं), और कुछ घर पहले से ही रंगे हुए हैं, इसलिए उन्हें फिर से रंगने की जरूरत नहीं है। जिन घरों का रंग समान है उन्हें नेबरहुड कहा जाता है। हमारे पास ऐ

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

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