กระเป๋าแบบแบ่งส่วนตามอัตราส่วน

มีสิ่งของที่มีมูลค่าและน้ำหนัก พร้อมกระเป๋าที่มี ความจุ จำกัด เป้าหมายคือบรรทุกมูลค่ารวมให้ได้มากที่สุด 🎒

ในรูปแบบ แบ่งส่วน คุณสามารถหยิบสิ่งของเพียงบางส่วนได้ เช่น เมล็ดพืชครึ่งกระสอบ อิสระนี้เองที่ทำให้วิธีแบบละโมบใช้ได้ผล

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

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

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

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

ความจุแต่ละหน่วยควรบรรจุมูลค่าให้ได้มากที่สุด ดังนั้นสิ่งของที่ มีความหนาแน่นสูงที่สุด ต้องมาก่อน การสลับเป็นสิ่งของที่มีความหนาแน่นต่ำกว่าจะทำให้สูญเสียมูลค่า

หากแบ่งสิ่งของไม่ได้ การเลือกแบบโลภตามอัตราส่วนจะใช้ไม่ได้ ปัญหาแบบ 0/1 ต้องใช้การโปรแกรมพลวัต ไม่ใช่การเรียงลำดับง่าย ๆ แบบนี้

การเรียงตามอัตราส่วนใช้เวลา O(n log n) และวงวนเติมของใช้เวลาเชิงเส้น ซึ่งเร็วเพียงพอสำหรับข้อจำกัดทั่วไปของการแข่งขัน

ใช้เลขจุดลอยตัวหรือเศษส่วนที่คำนวณได้อย่างแม่นยำสำหรับสิ่งของบางส่วน การตัดทอนแต่เนิ่น ๆ อาจทำให้ค่าลดลงและทำให้ได้คำตอบผิด

ลองนึกถึงการบรรทุก สินค้า การผสมเชื้อเพลิง หรือการแบ่งทรัพยากร เมื่อใดก็ตามที่สิ่งของแบ่งเป็นส่วน ๆ ได้ วิธีโลภตามอัตราส่วนคือเครื่องมือของคุณ

คุณกำลังบรรจุสิ่งของลงในกระเป๋าในปัญหากระเป๋าเป้แบบแบ่งได้

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