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

รุ่นแก้ไขเมื่อ 09:32, 3 ตุลาคม 2552

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

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

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

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

@@ แถว 3: / แถว 3: @@
 ดังนั้นกรณีที่ <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> แทนตำแหน่งแรกที่เราสามารถพิจารณาว่าจะตั้งร้านหรือไม่เป็นตำแหน่งต่อไป
+ส่วนกรณีที่ <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 ได้ดังนี้

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

รุ่นแก้ไขเมื่อ 09:32, 3 ตุลาคม 2552

รายการเลือกการนำทาง

เครื่องมือส่วนตัว

เนมสเปซ

สิ่งที่แตกต่าง

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ