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

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

इसलिए, यदि इनपुट है n = 7, cuts = [5,1,4,3], तो आउटपुट 16 होगा क्योंकि यदि हम उन्हें [3,5,1,4] की तरह क्रमबद्ध करते हैं, तो पहले लंबाई 7 में से 3 पर काटते हैं, इसलिए लागत 7 है, फिर हमारे पास लंबाई 3 और 4 के दो भाग हैं, फिर 5 पर काटते हैं, इसलिए लागत 4 है, अब तक कुल 7+4=11 है, फिर आकार 2 की छड़ी से 4 पर काटते हैं, इसलिए कुल लागत 7+4+2 = 13, फिर अंत में 3 पर काटते हैं इसलिए लागत 3 है, और अंतिम लागत 7+4+2+3 = 16।

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

cuts := एक सूची जहां cuts में तत्व क्रमबद्ध क्रम में हों, और शुरुआत में 0 डालें और अंत में n डालें
m := cuts का आकार
cost := m x m आकार का एक वर्ग मैट्रिक्स जिसे 0 से भरा गया हो
k को 2 से m - 1 तक के लिए, करें
- i को 0 से m - 1 तक के लिए, करें
  - j := i + k
  - यदि j >= m, तो
    - अगली पुनरावृत्ति के लिए जाएं
  - cost[i, j] = (cuts[j] - cuts[i]) + सभी s के लिए (cost[i, s] + cost[s, j]) का न्यूनतम जहां s range(i+1, j-1) में है
cost[0, m-1] वापस करें

उदाहरण

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

def solve(n, cuts):
    cuts = [0] + sorted(cuts) + [n]
    m = len(cuts)
    cost = [[0]*m for _ in range(m)]
    for k in range(2, m):
        for i in range(m):
            j = i + k
            if j >= m:
                continue
            cost[i][j] = (cuts[j]-cuts[i]) + min(cost[i][s] + cost[s][j] for s in range(i+1, j))
    return cost[0][m-1]

n = 7
cuts = [5,1,4,3]
print(solve(n, cuts))

इनपुट

7, [5,1,4,3]