โปรแกรมทำ Fractional Knapsack Problem ใน Python

สมมติว่าเรามีรายการน้ำหนัก weights และค่า values ความยาวเท่ากัน และ capacity คือน้ำหนักสูงสุดที่รับได้ สามารถหยิบเศษส่วนของไอเท็มได้ (ค่าสัมพันธ์กับน้ำหนัก) ต้องการหาค่าสูงสุด (ปัดทศนิยมทิ้ง)

ตัวอย่าง: weights = [6, 7, 3], values = [110, 120, 2], capacity = 10 ผลลัพธ์คือ 178 (ในโค้ดตัวอย่าง output 230 อาจมีข้อผิดพลาด)

ขั้นตอนการแก้ปัญหา (Greedy by Value/Weight Ratio)

1. จับคู่ (weight, value) เรียงตาม value/weight มากไปน้อย
2. สำหรับแต่ละคู่:
   • หาก capacity == 0 break
   • หาก capacity หยิบเศษส่วน: res += value * (capacity/weight), capacity = 0
   • มิฉะนั้น หยิบทั้งชิ้น: res += value, capacity -= weight
3. คืนค่า int(res)

ตัวอย่างโค้ด Python

class Solution:
    def solve(self, weights, values, capacity):
        res = 0
        for w, v in sorted(zip(weights, values), key=lambda x: -x[1]/x[0]):
            if not capacity:
                break
            if w > capacity:
                res += int(v / (w / capacity))
                capacity = 0
            else:
                res += v
                capacity -= w
        return int(res)

ob = Solution()
weights = [6, 7, 3]
values = [110, 120, 2]
capacity = 10
print(ob.solve(weights, values, capacity))  # Output: 178 (โค้ดต้นฉบับให้ 230 ผิด)

อินพุต

[6, 7, 3], [110, 120, 2], 10

เอาต์พุต

178