การตัดแท่ง
การตัดแท่ง (rod cutting) อัลกอริธึมการตัดไม้และวิธีการเพิ่มผลกำไรโดยใช้โปรแกรมแบบไดนามิก
ตัวอย่างการทำงานและวิธีคิด
ตัวอย่าง เรามีไม้มีขนาดความยาวเท่ากับ 8 และการตัดแต่ละท่อนจะมีราคาดังต่อไปนี้
| ความยาว | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| ราคา ($) | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 |
| ความยาว (i) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| ราคา ($) | 1 | 5 | 8 | 10 | 13 | 17 | 18 | 22 |
จะเห็นได้ว่าจาก ตารางราคาตามความยาวของท่อนไม้(เก่า) จะทำให้ไม้มีราคาสูงสุดแค่ $20 แต่จาก ตารางราคาตามความยาวของท่อนไม้(ใหม่) สามารถทำให้ไม้มีราคาสูงสุดถึง $22 โดยผ่านกระบวนการคิดโดยอัลกอริทึม Rod cutting และมีการคำนวญด้วยมือดังนี้
จากสูตร C(i) = max {Vk + C(i-k)} โดยที่ max = 1<k<i
C(1) = max : V(1) + c(1-1) = 1 + 0 = 1
ค่า max คือ 1
C(2) = max : V(1) + c(2-1) = 1 + 1 = 2
V(2) + c(1-1) = 5 + 0 = 5
ค่า max คือ 5
C(3) = max : V(1) + c(3-1) = 1 + 5 = 6
V(2) + c(2-1) = 5 + 1 = 6
V(3) + c(1-1) = 8 + 0 = 8
ค่า max คือ 8
C(4) = max : V(1) + c(4-1) = 1 + 8 = 9
V(2) + c(3-1) = 5 + 5 = 10
V(3) + c(2-1) = 8 + 1 = 9
V(4) + c(1-1) = 9 + 0 = 9
ค่า max คือ 10
C(5) = max : V(1) + c(5-1) = 1 + 10 = 11
V(2) + c(4-1) = 5 + 8 = 13
V(3) + c(3-1) = 8 + 5 = 13
V(4) + c(2-1) = 9 + 1 = 10
V(5) + c(1-1) = 10 + 0 = 10
ค่า max คือ 13
C(6) = max : V(1) + c(6-1) = 1 + 13 = 14
V(2) + c(5-1) = 5 + 10 = 15
V(3) + c(4-1) = 8 + 8 = 16
V(4) + c(3-1) = 9 + 5 = 14
V(5) + c(2-1) = 10 + 1 = 11
V(6) + c(1-1) = 17 + 0 = 17
ค่า max คือ 17
C(7) = max : V(1) + c(7-1) = 1 + 17 = 18
V(2) + c(6-1) = 5 + 13 = 18
V(3) + c(5-1) = 8 + 10 = 18
V(4) + c(4-1) = 9 + 8 = 17
V(5) + c(3-1) = 10 + 5 = 15
V(6) + c(2-1) = 17 + 1 = 18
V(7) + c(1-1) = 17 + 0 = 17
ค่า max คือ 18
C(8) = max : V(1) + c(8-1) = 1 + 18 = 19
V(2) + c(7-1) = 5 + 17 = 22
V(3) + c(6-1) = 8 + 13 = 21
V(4) + c(5-1) = 9 + 10 = 19
V(5) + c(4-1) = 10 + 8 = 18
V(6) + c(3-1) = 17 + 5 = 22
V(7) + c(2-1) = 17 + 1 = 18
V(8) + c(1-1) = 20 + 0 = 20
ค่า max คือ 22
จะเห็นได้ว่า ราคาที่สามารถทำได้สูงสุด คือ $22 เราสามารถจำหน่ายไม้ได้ 2 แบบ คือ แบบ 1 ท่อนความยาว 8 ที่ราคา $22 และ แบบ 2 ท่อน ที่ความยาว 2 และ 6 อย่างละท่อนที่ราคา $5 และ $17
ตัวอย่างโค้ดการตัดแท่ง (Rod Cutting) ในภาษาไพทรอน (python)
INT_MIN = -32767 def cut_rod(price): n = len(price) val = [0]*(n+1) 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 print val[i] return val[n] arr = [1,5,8,9,10,17,17,20] print("Maximum Obtainable Value is " + str(cut_rod(arr)))