ในบทความนี้ เราจะเรียนรู้วิธีการแก้ปัญหาต่อไปนี้:
ข้อความปัญหา — กำหนดไม้ยาว n และอาร์เรย์ราคาที่มีราคาของชิ้นส่วนทุกขนาดที่เล็กกว่า n ให้กำหนดค่าสูงสุดที่ได้จากการตัดไม้และขายชิ้นส่วน
เราจะใช้วิธี Dynamic Programming เพื่อแก้ปัญหานี้
มาเปลี่ยนดูโค้ดตัวอย่างด้านล่างนี้:
ตัวอย่างโค้ด
# Dynamic Programming solution for Rod cutting problem
INT_MIN = -32767
# ฟังก์ชันตัดไม้
def cutRod(price, n):
val = [0 for x in range(n + 1)]
val[0] = 0
# แบบ bottom-up
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
ตัวแปรทั้งหมดถูกประกาศในขอบเขตท้องถิ่น (local scope) และการอ้างอิงของมันแสดงในรูปภาพด้านบน
สรุป
ในบทความนี้ เราได้เรียนรู้วิธีการเขียนโปรแกรม Python สำหรับ Cutting a Rod โดยใช้ Dynamic Programming
