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

    solution

    Đề bài: [Toán cho CNTT] Bài toán khẩu phần ăn

    Bài toán khẩu phần (diet problem)

    Cần chọn số lượng x,yx, yx,y của hai loại thực phẩm sao cho tối thiểu chi phí c1x+c2yc_1 x + c_2 yc1​x+c2​y mà vẫn đáp ứng các yêu cầu dinh dưỡng aix+biy≥cia_i x + b_i y \ge c_iai​x+bi​y≥ci​ (đạm, calo, ...), với x,y≥0x,y\ge0x,y≥0.

    Ví dụ

    Chi phí 2x+3y2x + 3y2x+3y; yêu cầu x+2y≥6x + 2y \ge 6x+2y≥6 và 3x+y≥63x + y \ge 63x+y≥6. Tối ưu z=8.4z = 8.4z=8.4 tại giao điểm.

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

      Dòng 1: c1 c2 (chi phí). Dòng 2: n. n dòng a b c cho yêu cầu ax+by≥cax+by\ge cax+by≥c.

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

      1≤n≤201 \le n \le 201≤n≤20; hệ số nguyên trị tuyệt đối ≤100\le 100≤100.

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

      Chi phí tối thiểu (4 chữ số thập phân), hoặc NONE nếu vô nghiệm.

    Ví dụ:

    Đầu vào:

    2 3
2
1 2 6
3 1 6

    Đầu ra:

    9.6000

    Giải thích:

    Giao (1.2, 2.4) cho chi phi nho nhat 2*1.2+3*2.4=8.4.

    Đang tải editor...