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

    solution

    Đề bài: [Giải thuật] Cái túi 0/1

    Có nnn món đồ, món thứ iii có khối lượng wiw_iwi​ và giá trị viv_ivi​. Một cái túi sức chứa WWW. Hãy chọn tập con món đồ sao cho tổng khối lượng ≤W\le W≤W và tổng giá trị lớn nhất. In giá trị lớn nhất đó.

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

      Dòng đầu nnn và WWW. nnn dòng sau mỗi dòng wiw_iwi​ viv_ivi​.

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

      1≤n≤10001 \le n \le 10001≤n≤1000, 1≤W≤1041 \le W \le 10^41≤W≤104, 1≤wi≤W1 \le w_i \le W1≤wi​≤W, 1≤vi≤1091 \le v_i \le 10^91≤vi​≤109.

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

      In một số nguyên: tổng giá trị lớn nhất.

    Ví dụ:

    Đầu vào:

    3 5
2 3
3 4
4 5

    Đầu ra:

    7

    Giải thích:

    Chọn món 1 (w2,v3) và món 2 (w3,v4): tổng khối lượng 5<=5, giá trị 7 là lớn nhất.

    Đang tải editor...