ความคิดคือใช้ข้อเท็จจริงว่า Greedy approach ให้ best solution สำหรับ Fractional Knapsack problem
เพื่อเช็คว่า node ไหนสามารถให้ better solution ได้ เราคำนวณ optimal solution (ผ่าน node) โดย Greedy approach ถ้า solution จาก Greedy เองมากกว่า best so far แล้ว เราไม่สามารถได้ better solution ผ่าน node นั้น
Complete Algorithm ด้านล่าง −
Sort items ตาม decreasing order ของ ratio value/weight เพื่อ upper bound ด้วย Greedy
Initialize maxProfit = 0
สร้าง empty queue Q
สร้าง dummy node ของ decision tree enqueue เข้า Q profit และ weight = 0
ทำต่อไป while Q ไม่ว่าง
Extract item จาก Q ให้เป็น u
คำนวณ profit ของ next level node ถ้ามากกว่า maxProfit update maxProfit
คำนวณ bound ของ next level node ถ้ามากกว่า maxProfit add next level node เข้า Q
Consider case ที่ next level node ไม่ได้เป็นส่วนของ solution add node เข้า Q ด้วย level ถัดไป แต่ weight และ profit ไม่นับ next level nodes
Illustrations ด้านล่าง −
Input
// First thing in every pair is weight of item
// and second thing is value of item
Item arr1[] = {{2, 40}, {3.14, 50}, {1.98, 100}, {5, 95}, {3, 30}};
Knapsack Capacity W1 = 10
Output
The maximum possible profit = 235
