पायथन प्रोग्राम: रॉड काटना

इस लेख में हम दी गई समस्या के समाधान के बारे में जानेंगे।

समस्या कथन

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

हम समस्या को हल करने के लिए डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे।

उदाहरण

# रॉड काटने की समस्या के लिए डायनामिक प्रोग्रामिंग समाधान
INT_MIN = -32767

# कट फ़ंक्शन
def cutRod(price, n):
    val = [0 for x in range(n + 1)]
    val[0] = 0
    # बॉटम-अप तरीके से
    for i in range(1, n + 1):
        max_val = INT_MIN
        for j in range(i):
            max_val = max(max_val, price[j] + val[i-j-1])
        val[i] = max_val
    return val[n]

# मुख्य
arr = [2, 4, 7, 9, 11, 16, 16, 21]
size = len(arr)
print("Maximum Obtainable Value is " + str(cutRod(arr, size)))

आउटपुट

Maximum Obtainable Value is 21

निष्कर्ष

इस लेख में हमने रॉड काटने के पायथन प्रोग्राम के बारे में सीखा।