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

ให้ $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>