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

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

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

तो आउटपुट 65 होगा।

समाधान दृष्टिकोण

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

• res := 0
• horizontal := 1, vertical := 1
• i := 0, j := 0
• जब तक i < m और j < n:
  • यदि X_slice[i] > Y_slice[j]:
    • res := res + X_slice[i] * vertical
    • horizontal := horizontal + 1
    • i := i + 1
  • अन्यथा:
    • res := res + Y_slice[j] * horizontal
    • vertical := vertical + 1
    • j := j + 1
• total := 0
• जब तक i < m:
  • total := total + X_slice[i]
  • i := i + 1
• res := res + total * vertical
• total := 0
• जब तक j < n:
  • total := total + Y_slice[j]
  • j := j + 1
• res := res + total * horizontal
• res लौटाएं।

उदाहरण

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

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