แนวคิดคือการนำข้อเท็จจริงที่ว่าแนวทาง Greedy มาใช้เป็นทางออกที่ดีที่สุดสำหรับปัญหา Fractional Knapsack
เพื่อตรวจสอบว่าโหนดใดสามารถให้โซลูชันที่ดีกว่าแก่เราได้หรือไม่ เราคำนวณวิธีแก้ปัญหาที่เหมาะสมที่สุด (ผ่านโหนด) โดยใช้แนวทาง Greedy หากโซลูชันที่คำนวณโดยแนวทาง Greedy เป็นมากกว่าวิธีที่ดีที่สุด เราไม่สามารถหาวิธีแก้ปัญหาที่ดีกว่าผ่านโหนดได้
อัลกอริธึมที่สมบูรณ์ได้รับด้านล่าง -
-
จัดเรียงรายการทั้งหมดตามลำดับอัตราส่วนของมูลค่าต่อหน่วยน้ำหนักที่ลดลงเพื่อให้สามารถคำนวณขอบเขตบนโดยใช้ Greedy Approach
-
เริ่มต้นผลกำไรสูงสุด เช่น maxProfit =0
-
คิวว่าง Q ถูกสร้างขึ้น
-
โหนดจำลองของแผนผังการตัดสินใจจะถูกสร้างขึ้นและแทรกหรือจัดคิวให้กับ Q กำไรและน้ำหนักของโหนดจำลองจะเป็น 0
-
ติดตามขณะที่ Q ไม่ว่างหรือไม่ว่าง
-
มีการสร้างรายการจาก Q ให้ไอเทมที่สกัดออกมาเป็นคุณ
-
คำนวณกำไรของโหนดระดับถัดไป หากกำไรสูงกว่า maxProfit ให้แก้ไข maxProfit
-
คำนวณขอบเขตของโหนดระดับถัดไป หากขอบเขตสูงกว่า maxProfit ให้เพิ่มโหนดระดับถัดไปใน Q
-
พิจารณากรณีที่โหนดระดับถัดไปไม่ถือว่าหรือถือว่าเป็นส่วนหนึ่งของการแก้ปัญหา และเพิ่มโหนดไปยังคิวที่มีระดับเป็นถัดไป แต่น้ำหนักและกำไรโดยไม่พิจารณาหรือพิจารณาโหนดระดับถัดไป
-
ภาพประกอบด้านล่าง -
อินพุต
// First thing in every pair is treated as weight of item
// and second thing is treated as value of item
Item arr1[] = {{2, 40}, {3.14, 50}, {1.98, 100}, {5, 95}, {3, 30}};
Knapsack Capacity W1 = 10
ผลลัพธ์
The maximum possible profit = 235
