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

รุ่นแก้ไขปัจจุบันเมื่อ 10:38, 4 ตุลาคม 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 ได้ดังนี้

ให้ $FindQi\,$ เป็น subroutine ในการหา $q_{i}\,$ ให้กับแต่ละตำแหน่ง $i\,$ โดยค่าดังกล่าวจะเก็บไว้ในอะเรย์ $q\,$

<geshi lang="c"> FindQi(m,n)

   L = 0
   m[0] = - infinity
   i = 1
   while i <= n
       while m[i]-m[L] > k 
           L<--L + 1
       q[i] = L - 1
       i <-- i + 1

</geshi>

จากนั้นนำอะเรย์ $q\,$ ที่ได้ข้างต้นมาใช้ในการหาค่าการตั้งร้านที่ตำแหน่งต่าง ๆ เพื่อให้ได้กำไรมากที่สุดตาม recurrence ข้างต้นได้ดังนี้

<geshi lang="c"> Yuckdonald(m,n,q,k)

   M[0] = 0
   for i = 1 to n do
       M[i] = max(M[i-1],p[i]+M[q[i]])
   return M[n]

</geshi>

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

รุ่นแก้ไขปัจจุบันเมื่อ 10:38, 4 ตุลาคม 2552

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

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

เนมสเปซ

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

ดู

เพิ่มเติม

ค้นหา

การนำทาง

เครื่องมือ

@@ แถว 1: / แถว 1: @@
-ให้ <math> OPT(i) \,</math> คือผลรวมของกำไรที่มากที่สุดที่พิจารณาตำแหน่งการตั้ง
+ให้ <math> OPT(i) \,</math> คือผลรวมของกำไรที่มากที่สุดที่พิจารณาตำแหน่งการตั้งร้านจากตำแหน่งที่ 1 จนถึงตำแหน่งที่ <math> 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> 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> FindQi \,</math> เป็น subroutine ในการหา <math> q_i \,</math> ให้กับแต่ละตำแหน่ง <math> i \,</math> โดยค่าดังกล่าวจะเก็บไว้ในอะเรย์ <math> q \,</math>
-ใช้ตัวแปร <math> q_i \,</math> แทนตำแหน่งแรกที่เราสามารถพิจารณาว่าจะตั้งร้านหรือ
+<geshi lang="c">
+FindQi(m,n)
+    L = 0
+    m[0] = - infinity
+    i = 1
+    while i <= n
+        while m[i]-m[L] > k
+            L<--L + 1
+        q[i] = L - 1
+        i <-- i + 1
+</geshi>
-ไม่เป็นตำแหน่งต่อไป
+จากนั้นนำอะเรย์ <math> q \,</math> ที่ได้ข้างต้นมาใช้ในการหาค่าการตั้งร้านที่ตำแหน่งต่าง ๆ เพื่อให้ได้กำไรมากที่สุดตาม recurrence ข้างต้นได้ดังนี้
-เขียนเป็น pseudocode ได้ดังนี้
+<geshi lang="c">
+Yuckdonald(m,n,q,k)
+    M[0] = 0
+    for i = 1 to n do
+        M[i] = max(M[i-1],p[i]+M[q[i]])
+    return M[n]
+</geshi>