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

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

इसलिए, यदि इनपुट n =7, कट्स =[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.

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

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