Fractional Knapsack
การทดลองข้างล่างนี้เปรียบเทียบวิธีหาคำตอบของ fractional knapsack problem ที่ใช้วิธี greedy เหมือนกัน
คือค่อย ๆ เลือกของที่มีมูลค่าต่อน้ำหนักจากมากไปน้อย แต่จะต่างกันตรงที่
วิธีหนึ่ง เราเรียงลำดับของทุกชิ้นตามทูลค่าต่อน้ำหนักจากมากไปน้อย แล้วค่อย ๆ ไล่หยิบ
กับอีกวิธีหนึ่งอาศัย max heap เก็บของต่าง ๆ ที่จัดอันดับตามมูลค่าต่อน้ำหนัก
เสียเวลาสร้างฮีป แล้วค่อย ๆ removeMax ออกมาเก็บใส่ถุง
วิธีแรกจะคุ้มก็เมื่อผลท้ายสุดเราต้องหยิบของเป็นจำนวนมาก
ในขณะที่แบบใช้ max heap จะดีกว่าเมื่อหยิบของได้ไม่กี่ชิ้นเท่านั้น ก็เต็มความจุถุง
เราทดลองโดยเปลี่ยนค่าของน้ำหนักที่ถุงรับได้เป็น 1%, 10%, 20%, 50% และ 80% ของน้ำหนักรวมของของทุกชิ้น
W = 0.01 Σ wk
W = 0.1 Σ wk
W = 0.2 Σ wk
W = 0.5 Σ wk
W = 0.8 Σ wk
สมชาย ประสิทธิ์จูตระกูล