การตัดแท่ง

การตัดแท่ง (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)))