โปรแกรมหลามสำหรับตัดร็อด

ในบทความนี้ เราจะเรียนรู้เกี่ยวกับวิธีแก้ปัญหาตามที่ระบุด้านล่าง

แจ้งปัญหา − เราได้รับไม้เท้าที่มีความยาว 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

ตัวแปรทั้งหมดได้รับการประกาศในขอบเขตท้องถิ่นและการอ้างอิงของตัวแปรนั้นดูได้จากรูปด้านบน

บทสรุป

ในบทความนี้ เราได้เรียนรู้เกี่ยวกับวิธีการสร้างโปรแกรม Python สำหรับการตัดไม้เท้า