एक रॉड काटने के लिए पायथन कार्यक्रम

इस लेख में, हम नीचे दिए गए समस्या कथन के समाधान के बारे में जानेंगे।

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

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

आइए अब नीचे दिए गए कार्यान्वयन में समाधान देखें-

उदाहरण

# A Dynamic Programming solution for Rod cutting problem
INT_MIN = -32767
# cut function
def cutRod(price, n):
   val = [0 for x in range(n + 1)]
   val[0] = 0
   # bottom up manner
   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]
# main
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

सभी चर स्थानीय दायरे में घोषित किए गए हैं और उनके संदर्भ ऊपर दिए गए चित्र में देखे गए हैं।

निष्कर्ष

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