রড কাটিং সমস্যার পাইথন প্রোগ্রাম

এই আর্টিকেলে আমরা নিচের সমস্যা সমাধানের কথা শিখব।

সমস্যা: একটি রড দৈর্ঘ্য 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

সभी ভেরিয়েবল লোকাল স্কোপে ঘোষণা করা হয়েছে এবং তাদের রেফারেন্স উপরের চিত্রে দেখা যাচ্ছে।

উপসংহার

এই আর্টিকেলে আমরা শিখেছি কিভাবে রড কাটিং সমস্যার পাইথন প্রোগ্রাম লিখতে হয়।