Chương trình giải bài toán cái ba lô phân số trong Python

Cho danh sách , và dung lượng . Có thể lấy một phần vật phẩm (phân số) với giá trị tỷ lệ. Tìm giá trị lớn nhất (làm tròn xuống).

Ví dụ: , , → kết quả 230 (lấy hết vật 1: 110, vật 2: 120, tổng 230).

Giải thuật (Tham lam - Sắp xếp theo giá trị/trọng lượng)

1. Tạo danh sách cặp , sắp xếp giảm dần theo .
2. Duyệt các cặp:
   • Nếu : lấy hết, , .
   • Ngược lại: lấy phần , , , break.
3. Trả về .

Ví dụ minh họa

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 * (capacity / w))
                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: 230

Đầu vào

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

Đầu ra

230