Cardcaptor: /* นิยามค่า OPT \, */

2009-10-04T15:24:42Z

นิยามค่า OPT \,

Cardcaptor: หน้าที่ถูกสร้างด้วย '== นิยามค่า $OPT \,$ == ให้ $OPT(i) \,$ มีค่าเท่ากับผลรวมท…'

2009-10-04T15:23:09Z

หน้าที่ถูกสร้างด้วย '== นิยามค่า <math>OPT \,</math> == ให้ <math>OPT(i) \,</math> มีค่าเท่ากับผลรวมท…'

หน้าใหม่

== นิยามค่า <math>OPT \,</math> ==
ให้ <math>OPT(i) \,</math> มีค่าเท่ากับผลรวมที่มากที่สุดของลำดับย่อยที่ิคิดกันที่มีช่องสุดท้ายอยู่ที่ช่อง <math>a[i] \,</math> เราจะได้ว่า
: <math>OPT(i) = \begin{cases} a[1] & i = 1 \\ \max(a[i], OPT(i-1)+a[i]) & i > 1 \end{cases} \,</math>
เราสามารถพิสูจน์ว่าสมการข้่างบนเป็นจริงได้ด้วย induction ดังต่อไปนี้

(Base Case) ในกรณีนี้ <math>i = 1 \,</math> เราจะได้ว่ามีลำดับย่อยที่ติดกันที่จบที่ช่อง <math>a[1] \,</math> อยู่เพียงแค่ลำดับย่อยเดียว คือ ลำดับย่อยทีี่มีช่อง <math>a[1] \,</math> เีพียงช่องเดียว ฉะนั้น <math>OPT(1) = a[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>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>i \,</math> ทุกค่า

== การคำนวณค่า <math>OPT \,</math> ==
เราสามารถคำนวณตาราง <math>M[\cdot] \,</math> โดยที่ <math>M[i] = OPT(i) \,</math> ได้ดังต่อไปนี้
<geshi lang="C">
M[1] = a[1]
for i = 2 to n do
M[i] = max(a[i], M[i-1] + a[i])
</geshi>
เห็นได้อย่างชัดเจนว่าอัลกอรืทึมส่วนนี้ทำงานได้ในเวลา <math>O(n) \,</math>

== การหาช่วงที่มีผลบวกมากที่สุด ==
เราสามารถหาตำแหน่งของช่องสุดท้ายของช่วงที่มีผลบวกมากที่สุดได้ด้วยการหาค่า <math>j \,</math> ที่ทำให้ <math>M[j] \,</math> มากที่สุด

ที่เหลือคือเราจะต้องหาช่องที่ช่วงที่มีผลบวกมากที่สุดเริ่มต้น เราสามารถทำได้โดย pseudocode ต่อไปนี้
<geshi lang="C">
i = j
while (M[i] != a[i]) do
i = i - 1
</geshi>
ค่า <math>i \,</math> หลังจากที่ loop ทำงานเสร็จจะมีค่าเท่ากับช่องที่ช่วงที่มีผลบวกมากที่สุดเริ่มต้น

ที่เป็นเช่นนี้เพราะว่า จากสมการข้างบน <math>OPT(i) = a[i] \,</math> หากช่วงที่จบที่ <math>a[i] \,</math> นั้นเริ่มต้นจาก <math>a[i] \,</math> ด้วย มิเช่นนั้น <math>OPT(i) = OPT(i-1) + a[i] \,</math> ดังนั้นหากเราพบช่วงที่ <math>OPT(i) \neq a[i] \,</math> แสดงว่าช่วงที่จบที่ <math>a[i] \,</math> นั้นเกิดจากการเอาช่วงที่จบที่ <math>a[i-1] \,</math> มาต่อกับช่อง <math>a[i] \,</math> ดังนั้นเราจึงสามารถหาตำแหน่งเริ่มต้นของช่วงที่จบที่ <math>a[i] \,</math> ด้วยการไปหาตำแหน่งเริ่มต้นของช่วงที่จบที่ <math>a[i-1] \,</math> แทน

จาก pseudocode ข้างบน เราได้ว่าเราสามารถหาตำแหน่งสิ้นสุด <math>j \,</math> ของช่วงได้ในเวลา <math>O(n) \,</math> และหาตำแหน่งเริ่มต้น <math>i \,</math> ได้ในเวลา <math>O(n) \,</math> เช่นกัน ดังนั้นอัลกอริทึมทั้งหมดจึงทำงานได้ในเวลา <math>O(n) \,</math>

@@ แถว 8: / แถว 8: @@
 (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>a[i] \,</math> มาต่อกับช่อง <math>a[i+1] \,</math> ฉะนั้นผลรวมที่มากที่สุดของลำดับย่อยนี้คือ <math>OPT(i) + 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>

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

Cardcaptor: /* นิยามค่า OPT \, */

Cardcaptor: หน้าที่ถูกสร้างด้วย '== นิยามค่า OPT \, == ให้ OPT(i) \, มีค่าเท่ากับผลรวมท…'

Cardcaptor: หน้าที่ถูกสร้างด้วย '== นิยามค่า $OPT \,$ == ให้ $OPT(i) \,$ มีค่าเท่ากับผลรวมท…'