|
|
| แถว 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 ได้ดังนี้
| |
