Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Ba lô phân số

    Có nnn món đồ, món thứ iii có khối lượng wiw_iwi​ và giá trị viv_ivi​. Một chiếc ba lô chịu được tối đa khối lượng WWW. Khác với bài toán ba lô 0/1, ở đây bạn được phép lấy một phần của món đồ: nếu lấy tỉ lệ xxx (0≤x≤10 \le x \le 10≤x≤1) của món iii thì tốn x⋅wix \cdot w_ix⋅wi​ khối lượng và thu x⋅vix \cdot v_ix⋅vi​ giá trị.

    Hãy tìm tổng giá trị lớn nhất có thể bỏ vào ba lô. Chiến lược tham lam: ưu tiên các món có tỉ lệ giá trị trên khối lượng (vi/wiv_i / w_ivi​/wi​) cao nhất.

    In kết quả làm tròn tới đúng hai chữ số sau dấu phẩy.

    • Định dạng đầu vào:

      Dòng đầu chứa hai số nguyên nnn và WWW. Tiếp theo là nnn dòng, mỗi dòng chứa hai số nguyên wi viw_i\ v_iwi​ vi​.

    • Ràng buộc đầu vào:

      1≤n≤1051 \le n \le 10^51≤n≤105, 1≤W≤1091 \le W \le 10^91≤W≤109, 1≤wi≤1041 \le w_i \le 10^41≤wi​≤104, 1≤vi≤1041 \le v_i \le 10^41≤vi​≤104.

    • Định dạng đầu ra:

      In ra tổng giá trị lớn nhất, làm tròn tới 2 chữ số thập phân (ví dụ 240.00).

    Ví dụ:

    Đầu vào:

    3 50
10 60
20 100
30 120

    Đầu ra:

    240.00

    Giải thích:

    Lấy hết món 1 (60) và món 2 (100), rồi 20/30 món 3 (=80). Tổng 240.00.

    Đang tải editor...