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

    solution

    Đề bài: [Toán cho CNTT] Tối đa hàm mục tiêu trên tập đỉnh

    Tối đa trên các đỉnh

    Trong quy hoạch tuyến tính, nghiệm tối ưu luôn đạt tại một đỉnh của miền khả thi. Cho hàm mục tiêu z=c1x+c2yz = c_1 x + c_2 yz=c1​x+c2​y và danh sách các đỉnh, hãy tìm giá trị lớn nhất của zzz.

    Ví dụ

    Hàm z=x+yz = x + yz=x+y, các đỉnh (0,0),(4,0),(0,3)(0,0),(4,0),(0,3)(0,0),(4,0),(0,3): giá trị lớn nhất là 444 tại (4,0)(4,0)(4,0).

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

      Dòng 1: c1 c2. Dòng 2: số nguyên n. n dòng tiếp theo, mỗi dòng một đỉnh x y.

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

      1≤n≤10001 \le n \le 10001≤n≤1000.

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

      Giá trị lớn nhất của zzz, làm tròn 2 chữ số thập phân.

    Ví dụ:

    Đầu vào:

    1 1
3
0 0
4 0
0 3

    Đầu ra:

    4.00

    Giải thích:

    z tai cac dinh: 0, 4, 3. Lon nhat la 4.

    Đang tải editor...