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

Aoy: /* ข้อ 1 */

2009-09-21T13:11:19Z

ข้อ 1

Cardcaptor: /* ข้อ 3 */

2009-09-18T09:36:35Z

ข้อ 3

Cardcaptor: /* ข้อ 1 */

2009-09-18T06:00:59Z

ข้อ 1

Cardcaptor: /* ข้อ 3 */

2009-09-17T20:33:29Z

ข้อ 3

Cardcaptor: /* ข้อ 8 */

2009-09-17T20:32:53Z

ข้อ 8

Cardcaptor: /* ข้อ 7 */

2009-09-17T20:32:42Z

ข้อ 7

Cardcaptor: /* ข้อ 6 */

2009-09-17T20:32:31Z

ข้อ 6

Cardcaptor: /* ข้อ 6 */

2009-09-17T20:32:07Z

ข้อ 6

Cardcaptor: /* ข้อ 4 */

2009-09-17T20:31:49Z

ข้อ 4

Cardcaptor: /* ข้อ 5 */

2009-09-17T20:31:37Z

ข้อ 5

@@ แถว 1: / แถว 1: @@
 == ข้อ 1 ==
-[Kleinberg & Tardos 4.3] บริษัทรถบรรทุกบริษัทหนึ่งจัดการส่งพัสดุจากกรุงเทพฯ ไปสุไหงโกลก รสบรรทุกคันหนึ่งสามารถบรรทุกน้ำหนักได้ไม่เกิน W หน่วย ในวันหนึ่งๆ บริษัทจะได้รับกล่องพัสดุมาทีละกล่อง โดยกล่องที่ <math>i \,</math> จะมีน้ำหนัก <math>w_i \,</math> บริษัทมีนโยบายว่าของจะต้องถูกส่งตามลำดับที่บริษัทได้รับมา (กล่าวคือของที่มาก่อนจะต้องไม่ไปถึงหลังจากกล่องที่มาทีหลัง) ดังนั้นบริษัทจึงใช้อัลกอริทึมแบบ greedy ในการจัดของลงรถบรรทุกดังต่อไปนี้: บริษัทจะพยายามเอาของใส่รถบรรทุกคันหนึ่งตามลำดับที่ได้รับมาจนกระทั่งรถบรรทุกไม่สามารถบรรทุกของชิ้นต่อไปได้ แล้วจึงส่งรถบรรทุกเดินทางไปสุไหงโกลก ของที่มาหลังจากรถบรรทุกออกก็จะเอาไปใส่รถบรรทุกคันใหม่
+[Kleinberg & Tardos 4.3] บริษัทรถบรรทุกบริษัทหนึ่งจัดการส่งพัสดุจากกรุงเทพฯ ไปสุไหงโกลก รถบรรทุกคันหนึ่งสามารถบรรทุกน้ำหนักได้ไม่เกิน W หน่วย ในวันหนึ่งๆ บริษัทจะได้รับกล่องพัสดุมาทีละกล่อง โดยกล่องที่ <math>i \,</math> จะมีน้ำหนัก <math>w_i \,</math> บริษัทมีนโยบายว่าของจะต้องถูกส่งตามลำดับที่บริษัทได้รับมา (กล่าวคือของที่มาก่อนจะต้องไม่ไปถึงหลังจากกล่องที่มาทีหลัง) ดังนั้นบริษัทจึงใช้อัลกอริทึมแบบ greedy ในการจัดของลงรถบรรทุกดังต่อไปนี้: บริษัทจะพยายามเอาของใส่รถบรรทุกคันหนึ่งตามลำดับที่ได้รับมาจนกระทั่งรถบรรทุกไม่สามารถบรรทุกของชิ้นต่อไปได้ แล้วจึงส่งรถบรรทุกเดินทางไปสุไหงโกลก ของที่มาหลังจากรถบรรทุกออกก็จะเอาไปใส่รถบรรทุกคันใหม่
 บริษัทกังวลว่าเมื่อทำเช่นนี้แล้วจะมีจำนวนเที่ยวรถบรรทุกมากเกินไป โดยคิดว่า บางทีพวกเขาอาจจะทำให้จำนวนเที่ยวรถบรรทุกน้อยลงด้วยการส่งรถบรรทุกไปโดยที่มันยังสามารถใส่ของชิ้นต่อไปได้ การทำเช่นนี้อาจจะทำให้พวกเขาสามารถบรรจุของลงรถบรรทุกคันต่อไปได้ดียิ่งขึ้น

@@ แถว 20: / แถว 20: @@
 คุณต้องการตั้งสถานีส่งสัญญาณโทรศัพท์มือถือบนถนนนี้ โดยที่ทำให้บ้านทุกหลังอยู่ในรัศมี 4 กิโลเมตรของสถานีส่งสัญญาณอย่างน้อยหนึ่งสถานี
-จงออกแบบอัลกอริทึมเพื่อเลือกตำแหน่งกาตั้งสถานีส่งสัญญาณโทรศัพท์มือถือเพื่อให้บรรลุวัตถุประสงค์ข้างบน โดยมีจำนวนสถานีน้อยที่สุดเท่าที่จะเป็นไปได้ อัลกอริทึมของคุณควรจะทำงานได้ในเวลา <math>O(n) \,</math>
+จงออกแบบอัลกอริทึมเพื่อเลือกตำแหน่งการตั้งสถานีส่งสัญญาณโทรศัพท์มือถือเพื่อให้บรรลุวัตถุประสงค์ข้างบน โดยมีจำนวนสถานีน้อยที่สุดเท่าที่จะเป็นไปได้ อัลกอริทึมของคุณควรจะทำงานได้ในเวลา <math>O(n) \,</math>
 [[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมแบบตะกละ I/เฉลยข้อ 3|เฉลย]]

@@ แถว 1: / แถว 1: @@
 == ข้อ 1 ==
-[Kleinberg & Tardos 4.3] บริษัทรถบรรทุกบริษัทหนึ่งจัดการส่งพัีสดุจากกรุงเทพฯ ไปสุไหงโกลก รสบรรทุกคันหนึ่งสามารถบรรทุกน้ำหนักได้ไม่เกิน W หน่วย ในวันหนึ่งๆ บริษัทจะได้รับกล่องพัสดุมาทีละกล่อง โดยกล่องที่ <math>i \,</math> จะมีน้ำหนัก <math>w_i \,</math> บริษัทมีนโยบายว่าของจะต้องถูกส่งตามลำดับที่บริษัทได้รับมา (กล่าวคือของที่มาก่อนจะต้องไม่ไปถึงหลังจากกล่องที่มาทีหลัง) ดังนั้นบริษัทจึงใช้อัลกอริทึมแบบ greedy ในการจัดของลงรถบรรทุกดังต่อไปนี้: บริษัทจะพยายามเอาของใส่รถบรรทุกคันหนึ่งตามลำดับที่ได้รับมาจนกระทั่งรถบรรทุกไม่สามารถบรรทุกของชิ้นต่อไปได้ แล้วจึงส่งรถบรรทุกเดินทางไปสุไหงโกลก ของที่มาหลังจากรถบรรทุกออกก็จะเอาไปใส่รถบรรทุกคันใหม่
+[Kleinberg & Tardos 4.3] บริษัทรถบรรทุกบริษัทหนึ่งจัดการส่งพัสดุจากกรุงเทพฯ ไปสุไหงโกลก รสบรรทุกคันหนึ่งสามารถบรรทุกน้ำหนักได้ไม่เกิน W หน่วย ในวันหนึ่งๆ บริษัทจะได้รับกล่องพัสดุมาทีละกล่อง โดยกล่องที่ <math>i \,</math> จะมีน้ำหนัก <math>w_i \,</math> บริษัทมีนโยบายว่าของจะต้องถูกส่งตามลำดับที่บริษัทได้รับมา (กล่าวคือของที่มาก่อนจะต้องไม่ไปถึงหลังจากกล่องที่มาทีหลัง) ดังนั้นบริษัทจึงใช้อัลกอริทึมแบบ greedy ในการจัดของลงรถบรรทุกดังต่อไปนี้: บริษัทจะพยายามเอาของใส่รถบรรทุกคันหนึ่งตามลำดับที่ได้รับมาจนกระทั่งรถบรรทุกไม่สามารถบรรทุกของชิ้นต่อไปได้ แล้วจึงส่งรถบรรทุกเดินทางไปสุไหงโกลก ของที่มาหลังจากรถบรรทุกออกก็จะเอาไปใส่รถบรรทุกคันใหม่
 บริษัทกังวลว่าเมื่อทำเช่นนี้แล้วจะมีจำนวนเที่ยวรถบรรทุกมากเกินไป โดยคิดว่า บางทีพวกเขาอาจจะทำให้จำนวนเที่ยวรถบรรทุกน้อยลงด้วยการส่งรถบรรทุกไปโดยที่มันยังสามารถใส่ของชิ้นต่อไปได้ การทำเช่นนี้อาจจะทำให้พวกเขาสามารถบรรจุของลงรถบรรทุกคันต่อไปได้ดียิ่งขึ้น

@@ แถว 18: / แถว 18: @@
 [Kleinberg & Tardos 4.5] ถนนชนบทแห่งหนึ่งมีบ้านเรือนตั้งอยู่ริ่มถนนอยู่ <math>n \,</math> โดยบ้านหลังที่ <math>i \,</math> อยู่ห่างจากต้นถนนเป็นระยะทาง <math>x_i \,</math> กิโลเมตร เพื่อความสะดวก คุณสามารถสมมติได้ว่า <math>x_1 < x_2 < \ldots < x_{n-1} < x_n \,</math>
-คุณต้องการตั้งสถานีส่งสัญญาณโทรศัพท์มือถือบนถนนนี้ โดยที่ทำให้บ้านทุกหลังอยู่ในรัศมี 4 กิโลเมตรของสถานีส่งสัญญาณอย่างน้อยหนึ่งสถาีนี
+คุณต้องการตั้งสถานีส่งสัญญาณโทรศัพท์มือถือบนถนนนี้ โดยที่ทำให้บ้านทุกหลังอยู่ในรัศมี 4 กิโลเมตรของสถานีส่งสัญญาณอย่างน้อยหนึ่งสถานี
 จงออกแบบอัลกอริทึมเพื่อเลือกตำแหน่งกาตั้งสถานีส่งสัญญาณโทรศัพท์มือถือเพื่อให้บรรลุวัตถุประสงค์ข้างบน โดยมีจำนวนสถานีน้อยที่สุดเท่าที่จะเป็นไปได้ อัลกอริทึมของคุณควรจะทำงานได้ในเวลา <math>O(n) \,</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 20:32, 17 กันยายน 2552
แถว 96:		แถว 96:

	จงออกแบบอัลกอริทึมเพื่อจัดลำดับการทำงานเพื่อให้บรรลุวัตถุประสงค์ดังกล่าว		จงออกแบบอัลกอริทึมเพื่อจัดลำดับการทำงานเพื่อให้บรรลุวัตถุประสงค์ดังกล่าว
		+
		+	[[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมแบบตะกละ I/เฉลยข้อ 8\|เฉลย]]

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 20:32, 17 กันยายน 2552
แถว 87:		แถว 87:

	แล้วเราจะได้ว่าเราสามารถเลือกคนงานที่ทำงานกะตั้งแต่เวลา 18.00 น. - 22.00 น. เป็นผู้ตรวจงานได้ สังเกตว่ากะของคนงานคนนี้เหลื่อมกับกะของคนงานอื่นอีกทั้งสองคน		แล้วเราจะได้ว่าเราสามารถเลือกคนงานที่ทำงานกะตั้งแต่เวลา 18.00 น. - 22.00 น. เป็นผู้ตรวจงานได้ สังเกตว่ากะของคนงานคนนี้เหลื่อมกับกะของคนงานอื่นอีกทั้งสองคน
		+
		+	[[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมแบบตะกละ I/เฉลยข้อ 7\|เฉลย]]

	== ข้อ 8 ==		== ข้อ 8 ==

@@ แถว 69: / แถว 69: @@
 หลังจากนั้นคุณสามารถเช็คกรณีที่ <math>t = 3\,</math> และ <math>t = 4 \,</math> ได้ในทำนองเดียวกัน
 [[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมแบบตะกละ I/เฉลยข้อ 6|เฉลย]]
 == ข้อ 7 ==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 20:32, 17 กันยายน 2552
แถว 69:		แถว 69:

	หลังจากนั้นคุณสามารถเช็คกรณีที่ <math>t = 3\,</math> และ <math>t = 4 \,</math> ได้ในทำนองเดียวกัน		หลังจากนั้นคุณสามารถเช็คกรณีที่ <math>t = 3\,</math> และ <math>t = 4 \,</math> ได้ในทำนองเดียวกัน
		+
		+	[[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมแบบตะกละ I/เฉลยข้อ 6\|เฉลย]]

	จงออกแบบอัลกอริทึัมสำหรับแก้ปัญหาดังกล่าว เวลากาำรทำงานของอัลกอริทึมของคุณควรจะเป็น polynomial ในตัวแปร <math>n \,</math>		จงออกแบบอัลกอริทึัมสำหรับแก้ปัญหาดังกล่าว เวลากาำรทำงานของอัลกอริทึมของคุณควรจะเป็น polynomial ในตัวแปร <math>n \,</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 20:31, 17 กันยายน 2552
แถว 32:		แถว 32:

	ผู้จัดการแข่งขันต้องการจัดลำดับการเิริ่มว่ายน้ำของผู้เข้าแข่งขัน '''ให้ผู้เข้าแข่งขันคนที่แข่งขันเสร็จเป็นคนสุดท้าย แข่งขันเสร็จเร็วที่สุดเท่าที่จะทำได้''' จงออกแบบอัลกอริทึมที่มีประสิทธิืภาพเพื่อจัดลำดับการเริ่มต้นว่ายน้ำดังกล่าว		ผู้จัดการแข่งขันต้องการจัดลำดับการเิริ่มว่ายน้ำของผู้เข้าแข่งขัน '''ให้ผู้เข้าแข่งขันคนที่แข่งขันเสร็จเป็นคนสุดท้าย แข่งขันเสร็จเร็วที่สุดเท่าที่จะทำได้''' จงออกแบบอัลกอริทึมที่มีประสิทธิืภาพเพื่อจัดลำดับการเริ่มต้นว่ายน้ำดังกล่าว
		+
		+	[[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมแบบตะกละ I/เฉลยข้อ 4\|เฉลย]]

	== ข้อ 5 ==		== ข้อ 5 ==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 20:31, 17 กันยายน 2552
แถว 43:		แถว 43:

	จงออกแบบอัลกอริทึัมเพื่อคำนวณลำดับการทำงานที่ทำให้ความไม่พึงพอใจรวมต่ำที่สดเท่าที่จะทำได้		จงออกแบบอัลกอริทึัมเพื่อคำนวณลำดับการทำงานที่ทำให้ความไม่พึงพอใจรวมต่ำที่สดเท่าที่จะทำได้
		+
		+	[[418531 ภาคต้น 2552/โจทย์ปัญหาอัลกอริทึมแบบตะกละ I/เฉลยข้อ 5\|เฉลย]]

	== ข้อ 6 ==		== ข้อ 6 ==