knapsack

เป้

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

• วัตถุประสงค์: เพิ่มมูลค่าการขนส่งสินค้าให้สูงสุด (ผลรวมของมูลค่าของสินค้าที่เลือก)
• ข้อจำกัด: น้ำหนักบรรทุกรวม (ผลรวมของน้ำหนักของสินค้าที่เลือก) ต้องน้อยกว่าหรือเท่ากับความจุของตู้คอนเทนเนอร์

ตัวอย่างนี้แก้ปัญหา knapsack ดังกล่าวด้วยการปรับรูปแบบใหม่เป็นแบบจำลองกำลังสองแบบจำกัด (CQM) และส่งไปยังตัวแก้ปัญหา CQM แบบไฮบริด Leap

การใช้งาน

หากต้องการรันการสาธิตเริ่มต้น ให้ป้อนคำสั่ง:

python knapsack.py

หากต้องการดูตัวเลือกที่มี ให้ป้อนคำสั่ง:

python knapsack.py --help

อาร์กิวเมนต์บรรทัดคำสั่งให้คุณเลือกชุดข้อมูลชุดใดชุดหนึ่ง (ภายใต้โฟลเดอร์ /data ) และตั้งค่าความสามารถในการขนส่ง ไฟล์ข้อมูลได้รับการกำหนดเป็นแถวของรายการ โดยแต่ละรายการกำหนดเป็นคู่ของน้ำหนักและค่า

ภาพรวมรหัส

โค้ดใน knapsack.py มีฟังก์ชันหลัก 3 ฟังก์ชัน:

• build_knapsack_cqm() สร้าง CQM โดยการตั้งค่าวัตถุประสงค์และข้อจำกัดดังต่อไปนี้:

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

• parse_inputs() เป็นฟังก์ชันยูทิลิตี้ที่อ่านข้อมูลจากไฟล์ตัวอย่าง

• parse_solution() แยกวิเคราะห์และแสดงผลลัพธ์ที่ส่งคืนจากตัวแก้ปัญหา

ใบอนุญาต

เผยแพร่ภายใต้ Apache License 2.0 ดูไฟล์ใบอนุญาต