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

ข้อ 1

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

บริษัทกังวลว่าเมื่อทำเช่นนี้แล้วจะมีจำนวนเที่ยวรถบรรทุกมากเกินไป โดยคิดว่า บางทีพวกเขาอาจจะทำให้จำนวนเที่ยวรถบรรทุกน้อยลงด้วยการส่งรถบรรทุกไปโดยที่มันยังสามารถใส่ของชิ้นต่อไปได้ การทำเช่นนี้อาจจะทำให้พวกเขาสามารถบรรจุของลงรถบรรทุกคันต่อไปได้ดียิ่งขึ้น

เมื่อกำหนดลำดับของกล่องที่บริษัทได้รับพร้อมกับน้ำหนักของกล่องแต่ละกล่อง $w_{1},w_{2},\ldots ,w_{n}\,$ จงพิสูจน์ว่าอัลกอริทึมแบบ greedy ที่บริษัืทใช้อยู่นี้ทำให้จำนวนเที่ยวการส่งของน้อยที่สุดเท่าที่จะเป็นไปได้ การพิสูจน์ของคุณควรจะมีลักษณะคล้ายๆ กับการพิสูจน์ความถูกต้องของ greedy algorithm สำหรับแก้ปัญหา interval scheduling ซึ่งใช้เทคนิคการพิสูจน์แบบ "greedy algorithm นำหน้าเสมอ"

ข้อ 2

[Kleinberg & Tardos 4.4] กำหนด string $S\,$ และ $S'\,$ มาให้ เรากล่าวว่า $S'\,$ เป็น substring ของ $S\,$ ถ้าหากเราสามารถลบตัวอักษรบางตัวใน $S\,$ ออกแล้วได้ผลลัพธ์เท่ากับ $S'\,$ ยกตัวอย่างเช่น abc เป็น substring ของ daabaefcaf ( daabaefcaf )