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

อัลกอริทึม

เรียงงานของลูกค้าตาม $w_{i}/t_{i}\,$ จากมากไปหาน้อย แล้วถ่ายเอกสารตามลำดับนั้น จะได้ว่า อัลกอริทึมทำงานได้ในเวลา $O(n\log n)\,$ ซึ่งใช้ในการเรียงลำดับนั่นเอง

โจทย์ต้องการให้ความไม่พอใจรวมของลูกค้ามีค่าน้อยที่สุด เขียนเป็นสมการทางคณิตศาสตร์คือต้องการให้ค่า $C_{1}w_{1}+C_{2}w_{2}+...+C_{n}w_{n}\,$ มีค่าน้อยที่สุดนั่นเอง