पायथन में एक बोर्ड को वर्गों में काटने की न्यूनतम लागत

मान लीजिए हमारे पास लंबाई p और चौड़ाई q का एक बोर्ड है; हमें इस बोर्ड को p*q संख्या के वर्गों में तोड़ना है ताकि तोड़ने की लागत यथासंभव न्यूनतम हो। प्रत्येक किनारे के लिए काटने की लागत दी जाएगी।

इसलिए, यदि इनपुट X_slice =[3,2,4,2,5], Y_slice =[5,2,3]

तो आउटपुट 65

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

• res :=0
• क्षैतिज:=1, लंबवत:=1
• i :=0, j :=0
• जबकि मैं <एम और जे <एन, करते हैं
  • अगर X_slice[i]> Y_slice[j], तो
    • res :=res + X_slice[i] * लंबवत
    • क्षैतिज:=क्षैतिज + 1
    • i :=i + 1
  • अन्यथा,
    • res :=res + Y_slice[j] * क्षैतिज
    • ऊर्ध्वाधर:=लंबवत + 1
    • j :=j + 1
• कुल :=0
• जबकि मैं <एम, करते हैं
  • कुल :=कुल + X_slice[i]
  • i :=i + 1
• रेस :=रेस + टोटल * वर्टिकल
• कुल :=0
• जबकि j
• कुल :=कुल + Y_slice[j]
• j :=j + 1

उदाहरण

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

def minCost(X_slice, Y_slice, m, n):
   res = 0
   X_slice.sort(reverse = True)
   Y_slice.sort(reverse = True)
   horizontal = 1
   vertical = 1
   i = 0
   j = 0
   while i < m and j < n:
      if (X_slice[i] > Y_slice[j]):
         res += X_slice[i] * vertical
         horizontal += 1
         i += 1
      else:
         res += Y_slice[j] * horizontal
         vertical += 1
         j += 1
   total = 0
   while (i < m):
      total += X_slice[i]
      i += 1
   res += total * vertical
   total = 0
   while (j < n):
      total += Y_slice[j]
      j += 1
   res += total * horizontal
   return res
m = 6; n = 4
X_slice = [3,2,4,2,5]
Y_slice = [5,2,3]
print(minCost(X_slice, Y_slice, m-1, n-1))

इनपुट

[3,2,4,2,5],[5,2,3]

आउटपुट

65