Aoy: หน้าที่ถูกสร้างด้วย 'ให้ $OPT(i) \,$ เป็น penalty ที่น้อยที่สุดที่พิจารณาการเ…'

2009-10-03T09:43:30Z

หน้าที่ถูกสร้างด้วย 'ให้ <math> OPT(i) \,</math> เป็น penalty ที่น้อยที่สุดที่พิจารณาการเ…'

หน้าใหม่

ให้ <math> OPT(i) \,</math> เป็น penalty ที่น้อยที่สุดที่พิจารณาการเดินทางจากตำแหน่งที่ <math> i \,</math> ถึงตำแหน่งที่ <math> n \,</math>

พิจารณากรณีที่ <math> i = n \,</math> จะได้ว่า <math> OPT(n) = 0 \,</math>

กรณีที่ <math> i < n \,</math> จะได้ว่า <math> OPT(i) = min_{(i+1) \leq j \leq n}((200-(a_j - a_i))^2+OPT(j)) \,</math>

คือถ้าพิจารณาการเดินทางที่มาหยุดที่ตำแหน่งที่ <math> i \,</math> ใด ๆ ที่ไม่ใช่ตำแหน่งสุดท้ายแล้ว การตัดสินใจต่อไปคือจะไปหยุดที่ตำแหน่งไหนเป็นตำแหน่งต่อไป ซึ่งตำแหน่งที่เราสามารถหยุดได้คือ ตำแหน่งที่ <math> a_j \,</math> โดยที่ <math> (i+1) \leq j \leq n \,</math> นั่นเอง แล้วเราต้องเลือกหยุดตำแหน่งที่ทำให้ penalty น้อยที่สุดด้วย

เขียนเป็น pseudocode ได้ดังนี้

<geshi lang="c">
TRAVEL(a,n)
M[n] = 0
for i = 1 to n do
min = infinity
for j = i+1 to n do
if (200-(a[j]-a[i]))^2 + M[j] < min then
min = (200-(a[j]-a[i]))^2 + M[j]
M[i] = min
return M[0] // ส่ง ค่า M[0] เป็นคำตอบที่เป็น penalty ที่น้อยที่สุดที่พิจารณาการเดินทางจากตำแหน่ง 0 ไป n เป็นคำตอบ
</geshi>

418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I/เฉลยข้อ 2 - ประวัติรุ่นแก้ไข

Aoy: หน้าที่ถูกสร้างด้วย 'ให้ OPT(i) \, เป็น penalty ที่น้อยที่สุดที่พิจารณาการเ…'

Aoy: หน้าที่ถูกสร้างด้วย 'ให้ $OPT(i) \,$ เป็น penalty ที่น้อยที่สุดที่พิจารณาการเ…'