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

Aoy เมื่อ 10:38, 4 ตุลาคม 2552

2009-10-04T10:38:35Z

Aoy เมื่อ 10:28, 4 ตุลาคม 2552

2009-10-04T10:28:42Z

Aoy: ทำหน้าว่าง

2009-10-03T09:45:39Z

ทำหน้าว่าง

Aoy เมื่อ 09:32, 3 ตุลาคม 2552

2009-10-03T09:32:00Z

Aoy: หน้าที่ถูกสร้างด้วย 'ให้ $OPT(i) \,$ คือผลรวมของกำไรที่มากที่สุดที่พิจา…'

2009-10-03T09:13:59Z

หน้าที่ถูกสร้างด้วย 'ให้ <math> OPT(i) \,</math> คือผลรวมของกำไรที่มากที่สุดที่พิจา…'

หน้าใหม่

ให้ <math> OPT(i) \,</math> คือผลรวมของกำไรที่มากที่สุดที่พิจารณาตำแหน่งการตั้งร้านจากตำแหน่งที่ 1 จนถึงตำแหน่งที่ <math> i \,</math>

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

ส่วนกรณีที่ <math> i > 0 \,</math> จะได้ว่า <math> OPT(i) = max(OPT(i-1),p_i+OPT(q_i)) \,</math> เมื่อ <math> q_i \,</math> คือจำนวนเต็มที่มากที่สุดที่ทำให้ <math> m_i - m_{q_i} \geq k \,</math> นั่นคือการพิจารณาตำแหน่งที่ <math> i \,</math> เราก็มีทางเลือกอยู่สองทางคือตั้งร้านหรือไม่ตั้งร้าน ถ้าไม่ตั้งร้าน ดังนั้นตำแหน่งที่เราจะตั้งได้ก็ลดลงไปอีกหนึ่ง เหมือนกับไม่คิดถึงการตั้งร้านที่ตำแหน่งที่ <math> i\,</math> นี้นี่เอง ส่วนถ้าเลือกการตั้งร้านที่ตำแหน่งที่ <math> i \,</math> นี้ แน่นอนเราได้กำไรรวมแล้ว <math> p_i \,</math> หลังจากนั้นเราจะไม่สามารถตั้งร้านได้อีกภายในระยะ <math> k \,</math> จากร้านที่ตำแหน่งที่ <math> i \,</math> นี้ ซึ่งในที่นี้เราใช้ตัวแปร <math> q_i \,</math> แทนตำแหน่งแรกที่เราสามารถพิจารณาว่าจะตั้งร้านหรือไม่เป็นตำแหน่งต่อไป

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

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 09:45, 3 ตุลาคม 2552
แถว 1:		แถว 1:
−	ให้ <math> OPT(i) \,</math> คือผลรวมของกำไรที่มากที่สุดที่พิจารณาตำแหน่งการตั้งร้านจากตำแหน่งที่ 1 จนถึงตำแหน่งที่ <math> i \,</math>

−	~~ดังนั้นกรณีที่ <math> i = 0 \,</math> จะได้ว่า <math> OPT(0) = 0 \,</math>~~
−
−	ส่วนกรณีที่ <math> i > 0 \,</math> จะได้ว่า <math> OPT(i) = max(OPT(i-1),p_i+OPT(q_i)) \,</math> เมื่อ <math> q_i \,</math> คือจำนวนเต็มที่มากที่สุดที่ทำให้ <math> m_i - m_{q_i} > k \,</math> นั่นคือการพิจารณาตำแหน่งที่ <math> i \,</math> เราก็มีทางเลือกอยู่สองทางคือตั้งร้านหรือไม่ตั้งร้าน ถ้าไม่ตั้งร้าน ดังนั้นตำแหน่งที่เราจะตั้งได้ก็ลดลงไปอีกหนึ่ง เหมือนกับไม่คิดถึงการตั้งร้านที่ตำแหน่งที่ <math> i\,</math> นี้นี่เอง ส่วนถ้าเลือกการตั้งร้านที่ตำแหน่งที่ <math> i \,</math> นี้ แน่นอนเราได้กำไรรวมแล้ว <math> p_i \,</math> หลังจากนั้นเราจะไม่สามารถตั้งร้านได้อีกภายในระยะ <math> k \,</math> จากร้านที่ตำแหน่งที่ <math> i \,</math> นี้ ซึ่งในที่นี้เราใช้ตัวแปร <math> q_i \,</math> แทนตำแหน่งแรกที่เราสามารถพิจารณาว่าจะตั้งร้านหรือไม่เป็นตำแหน่งต่อไป
−
−	~~เขียนเป็น pseudocode ได้ดังนี้~~

@@ แถว 1: / แถว 1: @@
-ให้ <math> OPT(i) \,</math> คือผลรวมของกำไรที่มากที่สุดที่พิจารณาตำแหน่งการตั้ง
+ให้ <math> OPT(i) \,</math> คือผลรวมของกำไรที่มากที่สุดที่พิจารณาตำแหน่งการตั้งร้านจากตำแหน่งที่ 1 จนถึงตำแหน่งที่ <math> i \,</math>
 ดังนั้นกรณีที่ <math> i = 0 \,</math> จะได้ว่า <math> OPT(0) = 0 \,</math>
-ส่วนกรณีที่ <math> i > 0 \,</math> จะได้ว่า <math> OPT(i) = max(OPT(i-
+ส่วนกรณีที่ <math> i > 0 \,</math> จะได้ว่า <math> OPT(i) = max(OPT(i-1),p_i+OPT(q_i)) \,</math> เมื่อ <math> q_i \,</math> คือจำนวนเต็มที่มากที่สุดที่ทำให้ <math> m_i - m_{q_i} > k \,</math> นั่นคือการพิจารณาตำแหน่งที่ <math> i \,</math> เราก็มีทางเลือกอยู่สองทางคือตั้งร้านหรือไม่ตั้งร้าน ถ้าไม่ตั้งร้าน ดังนั้นตำแหน่งที่เราจะตั้งได้ก็ลดลงไปอีกหนึ่ง เหมือนกับไม่คิดถึงการตั้งร้านที่ตำแหน่งที่ <math> i\,</math> นี้นี่เอง ส่วนถ้าเลือกการตั้งร้านที่ตำแหน่งที่ <math> i \,</math> นี้ แน่นอนเราได้กำไรรวมแล้ว <math> p_i \,</math> หลังจากนั้นเราจะไม่สามารถตั้งร้านได้อีกภายในระยะ <math> k \,</math> จากร้านที่ตำแหน่งที่ <math> i \,</math> นี้ ซึ่งในที่นี้เราใช้ตัวแปร <math> q_i \,</math> แทนตำแหน่งแรกที่เราสามารถพิจารณาว่าจะตั้งร้านหรือไม่เป็นตำแหน่งต่อไป
-),p_i+OPT(q_i)) \,</math> เมื่อ <math> q_i \,</math> คือจำนวนเต็มที่มากที่สุดที่
+เขียนเป็น pseudocode ได้ดังนี้
-ในระยะ <math> k \,</math> จากร้านที่ตำแหน่งที่ <math> i \,</math> นี้ ซึ่งในที่นี้เรา
+ให้ <math> FindQi \,</math> เป็น subroutine ในการหา <math> q_i \,</math> ให้กับแต่ละตำแหน่ง <math> i \,</math> โดยค่าดังกล่าวจะเก็บไว้ในอะเรย์ <math> q \,</math>
-ใช้ตัวแปร <math> q_i \,</math> แทนตำแหน่งแรกที่เราสามารถพิจารณาว่าจะตั้งร้านหรือ
+<geshi lang="c">
-ไม่เป็นตำแหน่งต่อไป
+จากนั้นนำอะเรย์ <math> q \,</math> ที่ได้ข้างต้นมาใช้ในการหาค่าการตั้งร้านที่ตำแหน่งต่าง ๆ เพื่อให้ได้กำไรมากที่สุดตาม recurrence ข้างต้นได้ดังนี้
-เขียนเป็น pseudocode ได้ดังนี้
+<geshi lang="c">