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

เราให้หมายเลขรถโดยให้รถคันแรกที่ออกจากกรุงเทพฯ เป็นรถหมายเลข 1 รถคันที่สองที่ออกจากกรุงเทพฯ เป็นรถหมายเลข 2 เช่นนี้ไปเรื่อยๆ

ให้ S เป็นวิธีการจัดของลงรถสักวิธีหนึ่ง สำหรับของชิ้นที่ $i\,$ เราให้ $c_{i}^{S}\,$ แทนหมายเลขของรถคันที่ของชิ้นที่ $i\,$ ถูกบรรจุ สังเกตว่า $c_{n}^{S}\,$ คือจำนวนรถที่ใช้ในการขนส่งของทั้งหมด

ให้ $G\,$ เป็นวิธีการจัดของลงรถแบบ greedy ในโจทย์ และให้ $\mathrm {OPT} \,$ เป็นวิธีการจัดของลงรถที่ใช้รถจำนวนน้อยคันที่สุดเท่าที่จะเป็นไปได้ ดังนั้นเราทราบว่า $c_{n}^{\mathrm {OPT} }\leq c_{n}^{G}\,$

เราจะพิสูจน์ว่า $c_{i}^{G}\leq c_{i}^{\mathrm {OPT} }\,$ สำหรับ $i\,$ ทุกค่าที่ $1\leq i\leq n\,$ ซึ่งถ้าเราพิสูจน์ข้อความนี้ได้แล้ว เราจะได้ว่า $c_{n}^{G}=c_{n}^{\mathrm {OPT} }\,$ และนั่นหมายความว่า greedy algorithm ใช้รถน้อยค้นที่สุดเท่าที่จะเป็นไปได้แล้ว

การพิสูจน์ทำโดย strong induction บนตัวแปร i

(Base Case) ในกรณีนี้ $i=1\,$ เราได้ว่า $c_{1}^{G}=1\leq c_{1}^{\mathrm {OPT} }\,$ ดังนั้น base case เป็นความจริง

(Induction Case) สมมติว่ามีจำนวนเต็ม $i\geq 1\,$ ที่ทำให้ $c_{k}^{G}\leq c_{k}^{\mathrm {OPT} }\,$ สำหรับค่า $k\,$ ทุกค่าที่ $1\leq k\leq i\,$

พิจารณาการบรรจุของชิ้นที่ $i+1\,$ ลงรถบรรทุก กรณีนี้มีความเป็นไปได้สองกรณี

กรณีที่ 1: ถ้า $c_{i}^{G}<c_{i}^{\mathrm {OPT} }\,$ แล้วเราจะได้ว่า