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

202.29.77.40: /* ข้อ 3 */

2009-10-22T14:10:50Z

ข้อ 3

158.108.183.136: /* ข้อ 7 */

2009-10-05T10:16:57Z

ข้อ 7

Aoy: /* ข้อ 3 */

2009-10-04T10:28:22Z

ข้อ 3

Aoy: /* ข้อ 3 */

2009-10-03T09:47:26Z

ข้อ 3

Aoy: /* ข้อ 3 */

2009-10-03T09:47:05Z

ข้อ 3

Aoy: /* ข้อ 3 */

2009-10-03T09:46:43Z

ข้อ 3

Aoy: /* ข้อ 3 */

2009-10-03T09:46:17Z

ข้อ 3

Aoy: /* ข้อ 3 */

2009-10-03T09:46:07Z

ข้อ 3

Aoy: /* ข้อ 8 */

2009-10-03T06:02:24Z

ข้อ 8

Aoy: /* ข้อ 7 */

2009-10-03T06:02:12Z

ข้อ 7

@@ แถว 22: / แถว 22: @@
 == ข้อ 3 ==
-[Dasgupta, Papadimitriou, Vazirani 6.3] บัคโดนัลด์ (Yuckdonald's) กำลังวางแผนจะเปิดสาขใหม่บนถนน Quaint Valley Highway (QVH) โดยตำแหน่งในการตั้งสาขาที่เป็นไปได้ทั้งหมดมีอยู่ <math>n \,</math> คำแหน่ง อยู่บนเส้นตรงเส้นหนึ่ง และระยะทางของตำแหน่งเหล่านี้จากจุดเริ่มต้นของ QVH โดยเรียงจากน้อยไปหามาก คือ <math>m_1, m_2, \ldots, m_n \,</math> ตามลำดับ การตั้งสาขาใหม่ของยัคโดนัลด์จะต้องสอดคล้องกับเงื่อนไขต่อไปนี้
+[Dasgupta, Papadimitriou, Vazirani 6.3] บัคโดนัลด์ (Yuckdonald's) กำลังวางแผนจะเปิดสาขาใหม่บนถนน Quaint Valley Highway (QVH) โดยตำแหน่งในการตั้งสาขาที่เป็นไปได้ทั้งหมดมีอยู่ <math>n \,</math> คำแหน่ง อยู่บนเส้นตรงเส้นหนึ่ง และระยะทางของตำแหน่งเหล่านี้จากจุดเริ่มต้นของ QVH โดยเรียงจากน้อยไปหามาก คือ <math>m_1, m_2, \ldots, m_n \,</math> ตามลำดับ การตั้งสาขาใหม่ของยัคโดนัลด์จะต้องสอดคล้องกับเงื่อนไขต่อไปนี้
 * ที่ตำแหน่งทีเ่ป็นไปได้ตำแหน่งหนึ่งๆ ยัคโดนัลด์สามารถตั้งสาขาได้อยากมากเพียงสาขาเดียวเท่านั้น โดยหากตั้งสาขาที่ตำแหน่ง <math>m_i \,</math> แล้วยัคโดนัลด์จะได้กำไรโดยเฉลี่ยต่อวันเท่ากับ  <math>p_i \,</math> โดยที่ <math>p_i > 0 \,</math> สำหรับ <math>i = 1, 2, \ldots, n \,</math>
 * สาขาสองสาขาควรจะอยู่ห่างกันอย่างน้อย <math>k \,</math> กิโลเมตร โดยที่ <math>k \,</math> เป็นจำนวนเต็มบวก

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 10:16, 5 ตุลาคม 2552
แถว 82:		แถว 82:

	== ข้อ 7 ==		== ข้อ 7 ==
−	กำหนดสตริง <math>x = x_1x_2 \dotsb x_n \,</math> และ <math>y =y_1 y_2 \dotsb y_m \,</math> ~~เราต้องการหาความยาวของสับสตริงร่วมที่มีความยาวมากที่สุด~~ (longest common ~~substring~~) กล่าวคือ จำนวนเต็ม <math>k \,</math> ที่มีค่ามากที่สุดที่ทำให้มีดรรชนี <math>i_1 < i_2 < \dotsb < i_k \,</math> และ <math>j_1 < j_2 < \dotsb < j_k \,</math> ที่ทำให้ <math>x_{i_1} = y_{j_1}, x_{i_2} = y_{j_2}, x_{i_3} = y_{j_3}, \ldots, x_{i_k} = y_{j_k} \,</math> จงออกแบบอัลกอริทึมสำหรับแก้ปัญหานี้ อัลกอริทึมของคุณควรจะทำงานได้ในเวลา <math>O(mn) \,</math>	+	กำหนดสตริง <math>x = x_1x_2 \dotsb x_n \,</math> และ <math>y =y_1 y_2 \dotsb y_m \,</math> เราต้องการหาความยาวของลำดับร่วมที่มีความยาวมากที่สุด (longest common subsequence) กล่าวคือ จำนวนเต็ม <math>k \,</math> ที่มีค่ามากที่สุดที่ทำให้มีดรรชนี <math>i_1 < i_2 < \dotsb < i_k \,</math> และ <math>j_1 < j_2 < \dotsb < j_k \,</math> ที่ทำให้ <math>x_{i_1} = y_{j_1}, x_{i_2} = y_{j_2}, x_{i_3} = y_{j_3}, \ldots, x_{i_k} = y_{j_k} \,</math> จงออกแบบอัลกอริทึมสำหรับแก้ปัญหานี้ อัลกอริทึมของคุณควรจะทำงานได้ในเวลา <math>O(mn) \,</math>

@@ แถว 26: / แถว 26: @@
 * สาขาสองสาขาควรจะอยู่ห่างกันอย่างน้อย <math>k \,</math> กิโลเมตร โดยที่ <math>k \,</math> เป็นจำนวนเต็มบวก
 จงออกแบบอัลกอริทึมเพื่อคำนวณหาำกำไรเฉลี่ยต่อวันสูงสุดที่ยัคโดนัลด์จะได้จากการตั้งสาขา ณ ตำแหน่งต่างๆ ตามเงื่อนไขข้างบน
 == ข้อ 4 ==

@@ แถว 26: / แถว 26: @@
 * สาขาสองสาขาควรจะอยู่ห่างกันอย่างน้อย <math>k \,</math> กิโลเมตร โดยที่ <math>k \,</math> เป็นจำนวนเต็มบวก
 จงออกแบบอัลกอริทึมเพื่อคำนวณหาำกำไรเฉลี่ยต่อวันสูงสุดที่ยัคโดนัลด์จะได้จากการตั้งสาขา ณ ตำแหน่งต่างๆ ตามเงื่อนไขข้างบน
 == ข้อ 4 ==

@@ แถว 26: / แถว 26: @@
 * สาขาสองสาขาควรจะอยู่ห่างกันอย่างน้อย <math>k \,</math> กิโลเมตร โดยที่ <math>k \,</math> เป็นจำนวนเต็มบวก
 จงออกแบบอัลกอริทึมเพื่อคำนวณหาำกำไรเฉลี่ยต่อวันสูงสุดที่ยัคโดนัลด์จะได้จากการตั้งสาขา ณ ตำแหน่งต่างๆ ตามเงื่อนไขข้างบน
 == ข้อ 4 ==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 06:02, 3 ตุลาคม 2552
แถว 91:		แถว 91:
	# ข้อมูลนำเข้า: <math>x_1, x_2, \ldots, x_n, v \,</math>		# ข้อมูลนำเข้า: <math>x_1, x_2, \ldots, x_n, v \,</math>
	# ข้อมูลส่งออก: "ใช่" ถ้าคุณสามารถทอนเงิน <math>v \,</math> บาทได้โดยใชเหรียญ <math>x_1, \ldots, x_n \,</math> โดยใช้เหรียญชนิดละกี่เหรียญก็ได้ มิเช่นนี้ให้ตอบ "ไม่ใช่"		# ข้อมูลส่งออก: "ใช่" ถ้าคุณสามารถทอนเงิน <math>v \,</math> บาทได้โดยใชเหรียญ <math>x_1, \ldots, x_n \,</math> โดยใช้เหรียญชนิดละกี่เหรียญก็ได้ มิเช่นนี้ให้ตอบ "ไม่ใช่"
		+
		+	[[418531 ภาคต้น 2552/โจทย์ปัญหาการโปรแกรมพลวัต I/เฉลยข้อ 8\|เฉลย]]

@@ แถว 83: / แถว 83: @@
 == ข้อ 7 ==
 กำหนดสตริง <math>x = x_1x_2 \dotsb x_n \,</math> และ <math>y =y_1 y_2 \dotsb y_m \,</math> เราต้องการหาความยาวของสับสตริงร่วมที่มีความยาวมากที่สุด (longest common substring) กล่าวคือ จำนวนเต็ม <math>k  \,</math> ที่มีค่ามากที่สุดที่ทำให้มีดรรชนี <math>i_1 < i_2 < \dotsb < i_k \,</math> และ <math>j_1 < j_2 < \dotsb < j_k \,</math> ที่ทำให้ <math>x_{i_1} = y_{j_1}, x_{i_2} = y_{j_2}, x_{i_3} = y_{j_3}, \ldots, x_{i_k} = y_{j_k} \,</math> จงออกแบบอัลกอริทึมสำหรับแก้ปัญหานี้ อัลกอริทึมของคุณควรจะทำงานได้ในเวลา <math>O(mn) \,</math>
 == ข้อ 8 ==