วิธีแก้ปัญหา Fractional Knapsack ใน C ++

ปัญหาเป้แบบเศษส่วนในภาษา C++ หมายถึงการระบุวิธีการบรรจุสิ่งของที่มีน้ำหนักและกำไรที่กำหนดลงในกระเป๋าในลักษณะที่ทำให้กระเป๋ามีมูลค่าสูงสุดโดยไม่เกินขีดจำกัดสูงสุด

วิธีแก้ปัญหา Fractional Knapsack ใน C ++

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

อัลกอริทึมในการนำปัญหาเป้นเศษส่วนไปใช้

การทำงานของอัลกอริทึม Knapsack สามารถเข้าใจได้จากประเด็นต่อไปนี้:

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

แนวทางโลภในการแก้ปัญหากระเป๋าเป้สะพายหลังแบบเศษส่วน

แนวทางที่ละโมบมีจุดมุ่งหมายเพื่อสร้างทางเลือกที่เหมาะสมในแต่ละขั้นตอน ซึ่งจะนำไปสู่ทางออกที่ดีที่สุดในตอนท้าย แก้ปัญหาทีละขั้นตอนจนนำไปสู่ข้อสรุป แทนที่จะสรุปผลในตอนท้ายเท่านั้น นี่คือซอร์สโค้ดสำหรับการนำวิธีแก้ปัญหาเศษส่วนแบบแบ็คแพ็คมาใช้ใน C ++:

ในโค้ดนี้ มีการกำหนดโครงสร้างออบเจ็กต์ซึ่งมีค่าน้ำหนักและกำไรเก็บไว้ในนั้น bool cmp() ใช้เพื่อทำการเปรียบเทียบระหว่างวัตถุสองชิ้นโดยพิจารณาจากอัตราส่วนของน้ำหนักและมูลค่าของวัตถุทั้งสอง อาร์เรย์ถูกจัดเรียงตามลำดับจากมากไปน้อยและค่าจะเพิ่มขึ้นเรื่อยๆ จนกระทั่งถึงค่าสูงสุด หากค่าปัจจุบันได้รับอนุญาตและอยู่ภายในขีดจำกัด ค่านั้นจะถูกเพิ่ม มิฉะนั้น อัตราส่วนที่ลดลงจะถูกเพิ่มลงในถุง ขนาดของน้ำหนักและมูลค่าถูกป้อนไว้ในรหัสหลัก และกำไรสูงสุดจะถูกพิมพ์ลงบนเอาต์พุต

กำไรสูงสุดที่เก็บไว้ในขนมคือ 580

บทสรุป

ปัญหาเป้แบบเศษส่วนในภาษา C++ หมายถึงการระบุวิธีการบรรจุสิ่งของที่มีน้ำหนักและกำไรที่กำหนดลงในกระเป๋าในลักษณะที่ทำให้กระเป๋ามีมูลค่าสูงสุดโดยไม่เกินขีดจำกัดสูงสุด สิ่งนี้สามารถบรรลุได้ด้วยแนวทางโลภที่มีจุดมุ่งหมายเพื่อสร้างทางเลือกที่เหมาะสมในแต่ละขั้นตอน ซึ่งจะนำไปสู่ทางออกที่ดีที่สุดในตอนท้าย