ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I/เฉลยข้อ 1"
Cardcaptor (คุย | มีส่วนร่วม) (หน้าที่ถูกสร้างด้วย '== นิยามค่า <math>OPT \,</math> == ให้ <math>OPT(i) \,</math> มีค่าเท่ากับผลรวมท…') |
Cardcaptor (คุย | มีส่วนร่วม) |
||
| แถว 8: | แถว 8: | ||
(Induction Case) สมมติว่า <math>OPT(i) \,</math> มีค่าเท่ากับผลรวมที่มากที่สุดของลำดับย่ยอที่ติดกันที่มีช่องสุดท้ายอยู่ที่ช่อง <math>a[i] \,</math> สำหรับ <math>i \geq 1 \,</math> บางค่า พิจารณาลำดับย่อยที่มีผลบวกมากที่สุดจบที่ช่อง <math>a[i+1] \,</math> เราจะได้ว่ามีความเป็นไปได้สองกรณีด้วยกัน | (Induction Case) สมมติว่า <math>OPT(i) \,</math> มีค่าเท่ากับผลรวมที่มากที่สุดของลำดับย่ยอที่ติดกันที่มีช่องสุดท้ายอยู่ที่ช่อง <math>a[i] \,</math> สำหรับ <math>i \geq 1 \,</math> บางค่า พิจารณาลำดับย่อยที่มีผลบวกมากที่สุดจบที่ช่อง <math>a[i+1] \,</math> เราจะได้ว่ามีความเป็นไปได้สองกรณีด้วยกัน | ||
# ลำดับย่อยนั้นเริ่มต้นที่ช่อง <math>a[i+1] \,</math> ด้วย ในกรณีนี้ <math>OPT(i+1) = a[i+1] \,</math> | # ลำดับย่อยนั้นเริ่มต้นที่ช่อง <math>a[i+1] \,</math> ด้วย ในกรณีนี้ <math>OPT(i+1) = a[i+1] \,</math> | ||
| − | # | + | # ลำดับย่อยนั้นไม่ได้เริ่มต้นที่ช่อง <math>a[i+1] \,</math> ในกรณีนี้เราจะได้ว่าลำดับย่อยนั้นเกิดจากการนำเอาลำดับย่อยที่จบที่ช่อง <math>a[i] \,</math> มาต่อกับช่อง <math>a[i+1] \,</math> ฉะนั้นผลรวมที่มากที่สุดของลำดับย่อยนี้คือ <math>OPT(i) + a[i+1] \,</math> |
เมื่อรวมสองกรณีข้างบนเข้าด้วยกัน เราจะได้ว่า <math>OPT(i+1) = \max( a[i+1], OPT(i) + a[i+1] ) \,</math> | เมื่อรวมสองกรณีข้างบนเข้าด้วยกัน เราจะได้ว่า <math>OPT(i+1) = \max( a[i+1], OPT(i) + a[i+1] ) \,</math> | ||
รุ่นแก้ไขปัจจุบันเมื่อ 15:24, 4 ตุลาคม 2552
นิยามค่า
ให้ มีค่าเท่ากับผลรวมที่มากที่สุดของลำดับย่อยที่ิคิดกันที่มีช่องสุดท้ายอยู่ที่ช่อง เราจะได้ว่า
![{\displaystyle a[i]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/77c9a5a9d0b2cc5583d6d4f5ddfed5cb677cfcee)
![{\displaystyle OPT(i)={\begin{cases}a[1]&i=1\\\max(a[i],OPT(i-1)+a[i])&i>1\end{cases}}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd59234505ce85be25b9051ff838c5a8060931b6)
เราสามารถพิสูจน์ว่าสมการข้่างบนเป็นจริงได้ด้วย induction ดังต่อไปนี้
(Base Case) ในกรณีนี้ เราจะได้ว่ามีลำดับย่อยที่ติดกันที่จบที่ช่อง อยู่เพียงแค่ลำดับย่อยเดียว คือ ลำดับย่อยทีี่มีช่อง เีพียงช่องเดียว ฉะนั้น ตามต้องการ
![{\displaystyle a[1]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d8819f5d666e009e6c471b8878e8e5f56a01bea4)
![{\displaystyle OPT(1)=a[1]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4630cfbdc49794c88ecef38676f052796dfa8dd5)
(Induction Case) สมมติว่า มีค่าเท่ากับผลรวมที่มากที่สุดของลำดับย่ยอที่ติดกันที่มีช่องสุดท้ายอยู่ที่ช่อง สำหรับ บางค่า พิจารณาลำดับย่อยที่มีผลบวกมากที่สุดจบที่ช่อง เราจะได้ว่ามีความเป็นไปได้สองกรณีด้วยกัน
![{\displaystyle a[i+1]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6fda867fc7040c638dd396a829f2a1abfc470eaa)
- ลำดับย่อยนั้นเริ่มต้นที่ช่อง ด้วย ในกรณีนี้
- ลำดับย่อยนั้นไม่ได้เริ่มต้นที่ช่อง ในกรณีนี้เราจะได้ว่าลำดับย่อยนั้นเกิดจากการนำเอาลำดับย่อยที่จบที่ช่อง มาต่อกับช่อง ฉะนั้นผลรวมที่มากที่สุดของลำดับย่อยนี้คือ
![{\displaystyle OPT(i+1)=a[i+1]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/65c1c12f20eb21d5fbb0a64b608dff406a015b6a)
![{\displaystyle OPT(i)+a[i+1]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8d0f1489fe5aafad9c61ae955cbe92826b454bcb)
เมื่อรวมสองกรณีข้างบนเข้าด้วยกัน เราจะได้ว่า
![{\displaystyle OPT(i+1)=\max(a[i+1],OPT(i)+a[i+1])\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fab7c12b355cd768e84bc8af760cf665c1e05480)
ดั้งนั้นเราจึงสรุปได้ว่าสมการข้างบนเป็นจริงสำหรับค่า ทุกค่า
การคำนวณค่า
เราสามารถคำนวณตาราง โดยที่ ได้ดังต่อไปนี้ <geshi lang="C">
![{\displaystyle M[\cdot ]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cfb3571832e86e1b8899e759bb8a1ec800718e4d)
![{\displaystyle M[i]=OPT(i)\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d6f063f25ebb510eed95078ece7ae366041b690f)
M[1] = a[1]
for i = 2 to n do
M[i] = max(a[i], M[i-1] + a[i])
</geshi> เห็นได้อย่างชัดเจนว่าอัลกอรืทึมส่วนนี้ทำงานได้ในเวลา
การหาช่วงที่มีผลบวกมากที่สุด
เราสามารถหาตำแหน่งของช่องสุดท้ายของช่วงที่มีผลบวกมากที่สุดได้ด้วยการหาค่า ที่ทำให้ มากที่สุด
![{\displaystyle M[j]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/419475a82fa5ece74130df1e04d3f9460a135d0f)
ที่เหลือคือเราจะต้องหาช่องที่ช่วงที่มีผลบวกมากที่สุดเริ่มต้น เราสามารถทำได้โดย pseudocode ต่อไปนี้ <geshi lang="C">
i = j
while (M[i] != a[i]) do
i = i - 1
</geshi> ค่า หลังจากที่ loop ทำงานเสร็จจะมีค่าเท่ากับช่องที่ช่วงที่มีผลบวกมากที่สุดเริ่มต้น
ที่เป็นเช่นนี้เพราะว่า จากสมการข้างบน หากช่วงที่จบที่ นั้นเริ่มต้นจาก ด้วย มิเช่นนั้น ดังนั้นหากเราพบช่วงที่ แสดงว่าช่วงที่จบที่ นั้นเกิดจากการเอาช่วงที่จบที่ มาต่อกับช่อง ดังนั้นเราจึงสามารถหาตำแหน่งเริ่มต้นของช่วงที่จบที่ ด้วยการไปหาตำแหน่งเริ่มต้นของช่วงที่จบที่ แทน
![{\displaystyle OPT(i)=a[i]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8d69a807ca60ecb3a165553397917d1bde4b5437)
![{\displaystyle OPT(i)=OPT(i-1)+a[i]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8421e8e09db91a3808ee41979205be05289d9273)
![{\displaystyle OPT(i)\neq a[i]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7100f95707dcd16298a7e6a2f22c7baa7c66499a)
![{\displaystyle a[i-1]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6e8b55512d464b0c5f3fcab40f0f8930d0ed74e2)
จาก pseudocode ข้างบน เราได้ว่าเราสามารถหาตำแหน่งสิ้นสุด ของช่วงได้ในเวลา และหาตำแหน่งเริ่มต้น ได้ในเวลา เช่นกัน ดังนั้นอัลกอริทึมทั้งหมดจึงทำงานได้ในเวลา
